Республиканская олимпиада по информатике 2008 год

Есеп D. Түсқағаз

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

Жұмысшыларға ені $X$, биіктігі $Y$ болатын қабырғаны түсқағазбен жабыстыру керек. Түсқағаздың әрбір рулоны ені $A$, ал биіктігі $B$ сантиметрді құрайды. Әрбір рулон биіктіктері бірдей B горизонталь жолдарға бөлінген. Жолдардың барлығы келесі ретпен K түрлі түске боялған (жолдар төменнен жоғары қарай нөмірленеді):
1, K+1, 2K+1, .. нөміріндегі жолдар 1 нөмірлі түске;
2, K+2, 2K+2, .. нөміріндегі жолдар 2 нөмірлі түске;
...
K, 2K, 3K, .. нөміріндегі жолдар $K$ нөмірлі түске боялған.
Горизонталь бойынша тұрған көршілес жолдардың түстері сәйкес келетіндей, ал вертикаль бойынша түстер дәл рулондағыдай кездесіп отыратындай етіп түсқағазды қабырғаға жабыстыру керек (алайда төменгі жолдың түсі кез- келген бола алады). Берілген қабырғадан алдынғы қабырғаларды толық жабыстырып болғаннан кейін $N$ қалдық рулон қалды. Әрбір қалған қалдықтың ені рулонның енімен бірдей. Берілген шарттарды қанағаттандыратын және осы қабырғаны толық жабатындай ең аз дегенде қаншама бүтін рулон сатып алу керек? Бүтін емес рулонды сатып алуға болмайды. Түсқағаздарды жолдардың шекаралары бойынша ғана қырқуға болады.

Формат входного файла

Кіріс файлдың бірінші жолы алты бүтін оң саннан тұрады $X$, $Y$, $A$, $B$, $K$, $N$ (1 <= $X$, $Y$, $A$, $B$ <= $10^9$, 1 <= $K, N$ <= $5 * 10^5$, $X mod A = 0$, $B mod K = 0$). Келесі $N$ жолдың әрқайсысында екі бүтін сан жазылған: біріншісі— қалдықтың төменгі жолындағы түс нөмірі, екіншісі – қалдықтың биіктігі (сантиметрмен берілген). Әрбір қалдық – бүтін рулонның бөгілі болатынына кепіл беріледі. Жолдағы сандар бос орын арқылы бөлінген.

Формат выходного файла

Шығыс файлға бір бүтін сан жазылу керек – ең аз дегендегі сатып алынатын рулондар саны.

Пример:

Вход

5 5 1 10 10 10
6 4
6 2
3 3
2 4
10 1
5 2
6 2
8 3
2 5
2 5

Ответ

2