| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 1 | 1 | 1 | 100.000% |
Как всем известно, миньоны очень любят бананы, поэтому Грю постоянно сталкивается с необходимостью их закупать. Так как миньонов очень много, он хочет знать количество бананов, которое он закупит.
Он покупает бананы в интернет-магазинах с доставкой на дом. У данного способа есть один спецэффект: если оплачивать коробку бананов в момент отправки, то ее стоимость будет $C_1,ドル а если при получении, то $C_2$. Грю взломал сервера всех интернет-магазинов по продаже бананов и узнал данные о продажах в ближайшее время. Теперь он знает про каждую коробку бананов, когда ее смогут отправить и когда она придет к нему. Также у него есть выписка из банка, в которой написано, когда и сколько ему поступит денег на счет.
Грю очень нетерпеливый, поэтому если он может купить коробку бананов в момент отправки (у него есть деньги на счету, и их хватает для покупки), то он покупает. В противном случае он вызывает курьера, и если в момент доставки Грю может выкупить, то он выкупает, если нет, то курьер уходит ни с чем. Также Грю знает, что в один момент времени ему не придется выбирать из нескольки коробок, какую купить.
Так как помимо миньонов Грю растит еще трех девочек, у него не остается времени на расчеты. Он просит вас написать программу, которая по имеющимся у него данным вычислит, какое количество коробок бананов он в итоге купит.
В первой строке входного файла содержатся два целых числа $C_1,ドル $C_2$ (1ドル \le C_1 \le C_2 \le 1000$) --- стоимости коробки бананов в момент отправки и в момент получения. Во второй строке входного файла находится одно целое число $n$ (1ドル \le n \le 100,000円$) --- количество платежей, поступающих на счет Грю. В следющих $n$ строках записаны пары чисел $a_i,ドル $t_i$ (1ドル \le a_i \le 1000, 1 \le t_i \le 1,000円,000円,000円$) --- количество поступающих денег и время, когда они поступят. В $n + 3$ строке входного файла дано число $m$ (1ドル \le m \le 100,000円$) --- количество коробок бананов, которые будут продаваться в ближайшее время. В следующих $m$ строках записаны пары чисел $l_i,ドル $r_i$ (1ドル \le l_i \le r_i \le 1,000円,000円,000円$) --- время отправки и время получения каждой коробки бананов. Для любых $i \ne j$ выполняется $l_i \ne r_j,ドル $r_i \ne r_j,ドル $l_i \ne l_j$.
В единственной строке выходного файла количество коробок бананов, которые Грю сможет купить.
100 200 3 100 1 200 10 400 21 4 12 22 2 4 5 23 8 19
3
В примере Грю будет действовать следующим способом:
В конце баланс счета будет 300.