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