29876번 - Täpilised ribad 다국어

Jukul on $L$ 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 $M$ ruutu ja millel on igaühel täpselt $N$ täppi. Riba tohib lõigata ainult ruutude vahekohtadest.

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

Järgneval $T$ 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 $1$ kuni $1\,000$ täppi.

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