Դդում
Դավիթը աշնանային արձակուրդին օգնում է տատիկին և դդում է աճեցնում։ Նրա կախարդական հողամասում կա
N հատ դդում։ Յուրաքանչյուր դդմի մասին հայտնի է նրա սկզբնական s[i] քաշը և աճելու t[i] տեմպը։ Որպեսզի դդումները լավ մեծանան Դավիթը կճուճով ջուր է բերում Սառնաղբյուրից, որն այնքան էլ մոտ չէ հողամասին։ Ամեն անգամ բերած ջրով նա միայն մեկ դդում է ջրում և այդ դդումի քաշն անմիջապես մեծանում է t[i]-ով։ Արձակուրդի բոլոր օրերի ընթացքում Դավիթն այդպես կարող է Սառնաղբյուրից K անգամ ջուր բերել։Տատիկը համարում է, որ դդումը բավականաչափ մեծացած է, եթե նրա քաշը առնվազն
M է։ Արձակուրդի ընթացքում Դավիթը առավելագույն քանի՞ դդում կարող է բավականաչափ մեծացնել։Մուտքային տվյալներ
Առաջին տողում տրված են դդումների
N (1 ≤ N ≤ 100 000) քանակը, ջուր բերելու K M s[i] քաշը և աճելու t[i] տեմպը Ելքային տվյալներ
Պետք է արտածել մեկ թիվ՝ բավականաչափ մեծացած դդումների առավելագույն քանակը։
Օրինակ
Մուտք. | Ելք. |
3 4 5
1 1
2 1
3 2 | 2 |
3 5 4
0 2
6 1
3 0 | 2 |
Աղբյուրը՝ Դպրոցական 2022
Constraints
Time limit: 0.2 seconds
Memory limit: 512 MB
Output limit: 1 MB