Täpilised ribad

시간 제한3초메모리 제한1024 MB

요약

L칸짜리 띠의 일부 칸에 점이 있고, 각 구간에 점이 정확히 N개씩 들어가도록 길이 M인 조각을 최대 몇 개로 자를 수 있는지 구한다.

난이도: 보통10점 중 6점
유형: 그리디, 누적 합, 이분 탐색, 구현
정답자: 아직 제출이 없습니다

문제

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.

예제1

예제 1

입력

예상 출력