Դավիթը աշնանային արձակուրդին օգնում է տատիկին և դդում է աճեցնում։ Նրա կախարդական հողամասում կա N հատ դդում։ Յուրաքանչյուր դդմի մասին հայտնի է նրա սկզբնական s[i] քաշը և աճելու t[i] տեմպը։ Որպեսզի դդումները լավ մեծանան Դավիթը կճուճով ջուր է բերում Սառնաղբյուրից, որն այնքան էլ մոտ չէ հողամասին։ Ամեն անգամ բերած ջրով նա միայն մեկ դդում է ջրում և այդ դդումի քաշն անմիջապես մեծանում է t[i]-ով։ Արձակուրդի բոլոր օրերի ընթացքում Դավիթն այդպես կարող է Սառնաղբյուրից K անգամ ջուր բերել։
Տատիկը համարում է, որ դդումը բավականաչափ մեծացած է, եթե նրա քաշը առնվազն M է։ Արձակուրդի ընթացքում Դավիթը առավելագույն քանի՞ դդում կարող է բավականաչափ մեծացնել։
Մուտքային տվյալներ
Առաջին տողում տրված են դդումների N (1 ≤ N ≤ 100 000) քանակը, ջուր բերելու K քանակը և M սահմանային արժեքը։ Հաջորդ N տողերից յուրաքանչյուրում տրված են երկուական թվեր՝ հերթական դդմի նախնական s[i] քաշը և աճելու t[i] տեմպը ։
Ելքային տվյալներ
Պետք է արտածել մեկ թիվ՝ բավականաչափ մեծացած դդումների առավելագույն քանակը։