| Ուղարկել | Բոլոր լուծումները | Լավագույն լուծումները | Վերադառնալ ցուցակին |
PUMPKIN - Դդում |
Դավիթը աշնանային արձակուրդին օգնում է տատիկին և դդում է աճեցնում։ Նրա կախարդական հողամասում կա N հատ դդում։ Յուրաքանչյուր դդմի մասին հայտնի է նրա սկզբնական s[i] քաշը և աճելու t[i] տեմպը։ Որպեսզի դդումները լավ մեծանան Դավիթը կճուճով ջուր է բերում Սառնաղբյուրից, որն այնքան էլ մոտ չէ հողամասին։ Ամեն անգամ բերած ջրով նա միայն մեկ դդում է ջրում և այդ դդումի քաշն անմիջապես մեծանում է t[i]-ով։ Արձակուրդի բոլոր օրերի ընթացքում Դավիթն այդպես կարող է Սառնաղբյուրից K անգամ ջուր բերել։
Տատիկը համարում է, որ դդումը բավականաչափ մեծացած է, եթե նրա քաշը առնվազն M է։ Արձակուրդի ընթացքում Դավիթը առավելագույն քանի՞ դդում կարող է բավականաչափ մեծացնել։
Մուտքային տվյալներ
Առաջին տողում տրված են դդումների N (1 ≤ N ≤ 100 000) քանակը, ջուր բերելու K (1 ≤ K ≤ 109) քանակը և M (1 ≤ M ≤ 109) սահմանային արժեքը։ Հաջորդ N տողերից յուրաքանչյուրում տրված են երկուական թվեր՝ հերթական դդմի նախնական s[i] քաշը և աճելու t[i] տեմպը (0 ≤ s[i], t[i] ≤ 109)։
Ելքային տվյալներ
Պետք է արտածել մեկ թիվ՝ բավականաչափ մեծացած դդումների առավելագույն քանակը։
Օրինակներ
| Մուտք | Ելք |
|---|---|
| 3 4 5 1 1 2 1 3 2 |
2 |
| Մուտք | Ելք |
| 3 5 4 0 2 6 1 3 0 |
2 |
| Ավելացրեց. | Andreasyan |
| Ամսաթիվ. | 2021-12-04 |
| Ժամանակի սահմանափակումը. | 0.100s |
| Ծրագրի տեքստի սահմանափակումը. | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Լեզուներ. | C CSHARP C++ 4.3.2 CPP CPP14 JAVA PAS-GPC PAS-FPC PYTHON3 |
| Աղբյուրը. | Դպրոցական փուլ, 2021-22 |
RSS