Со счета мобильного телефона Аркадия каждый день утром снимают p рублей. Среди следующих m дней есть n дней, когда Аркадий пополнит счет: в день di он положит ti рублей. Аркадий всегда пополняет счет до снятия денег за этот день. Других пополнений или снятий в течение следующих m дней не будет происходить.
Определите количество дней с 1-го по m-й, в которые на счету Аркадия будет отрицательная сумма денег после ежедневного платежа (т. е. вечером). Считайте, что изначально на счету Аркадия ноль рублей.
Выходные данные
Выведите количество дней с 1-го по m-й, в которые на счету Аркадия будет отрицательная сумма денег после ежедневного платежа.
Примечание
В первом примере баланс счета выглядит следующим образом (изначально баланс нулевой):
- в первый день списывается 6 рублей, баланс в конце дня равен - 6;
- во второй день Аркадий пополняет счет на 13 рублей, после этого списывается 6 рублей, баланс в конце дня равен 1;
- в третий день списывается 6 рублей, баланс в конце дня равен - 5;
- в четвертый день Аркадий пополняет счет на 20 рублей, после этого списывается 6 рублей, баланс в конце дня равен 9;
- в пятый день списывается 6 рублей, баланс в конце дня равен 3;
- в шестой день списывается 6 рублей, баланс в конце дня равен - 3;
- в седьмой день Аркадий пополняет счет на 9 рублей, после этого списывается 6 рублей, баланс в конце дня равен 0.
Таким образом, в конце первого, третьего и шестого дней баланс счета Аркадия был отрицательным.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 6 7
2 13
4 20
7 9
|
3
|
|
2
|
5 4 100
10 70
15 76
21 12
30 100
67 85
|
26
|