Täpilised ribad

문제

Jukul on $LL$ ruudust koosnev pabeririba, mille osadel ruutudel on täpid. Juku soovib lõigata riba juppideks nii, et tekiks võimalikult palju juppe, mille pikkus on täpselt $MM$ ruutu ja millel on igaühel täpselt $NN$ täppi. Riba tohib lõigata ainult ruutude vahekohtadest.

입력

Esimesel real on tühikutega eraldatuna algse riba pikkus $LL$ ($1\le L\le {10}^{15}1\; \backslash le\; L\; \backslash le\; 10^\{15\}$), täppidega ruutude arv $TT$ ($0\le T\le {10}^{5}0\; \backslash le\; T\; \backslash le\; 10^5$), soovitud juppide pikkus $MM$ ($1\le M\le {10}^{6}1\; \backslash le\; M\; \backslash le\; 10^6$) ja igal jupil soovitud täppide arv $NN$ ($0\le N\le {10}^{9}0\; \backslash le\; N\; \backslash le\; 10^9$). Ruudud on nummerdatud $1\dots L1\; \backslash ldots\; L$ alustades riba otsast.

Järgneval $TT$ real on igaühel kaks täisarvu: ühe täppidega ruudu number ja täppide arv sellel ruudul. Täppidega ruutude andmed on antud ruutude numbrite kasvavas järjekorras ja neil on igaühel $11$ kuni $10001\backslash ,000$ täppi.

출력

Ainsale reale väljastada üks täisarv: mitu soovitud omadustega juppi saab Juku oma ribast lõigata.