Будучи физиком, Чарли любит планировать свою жизнь в простых и точных терминах.
В течение следующих \(m\) месяцев, начиная с нулевой суммы денег, Чарли будет усердно работать и зарабатывать \(x\) фунтов в месяц. Для \(i\)-го месяца \((1 \le i \le m)\) будет одна возможность потратить сумму \(c_i\) фунтов, чтобы получить счастье \(h_i\).
Запрещено брать в долг. Заработанные деньги в \(i\)-м месяце можно тратить только в более поздний месяц \(j\) (\(j>i\)).
Поскольку физики не пишут код, помогите Чарли найти максимально возможную сумму счастья.
Выходные данные
Для каждого набора входных данных выведите одно целое число, максимальную сумму счастья, которую мог бы получить Чарли.
Примечание
В первом примере Чарли получает зарплату только в конце месяца, поэтому не может позволить себе ничего купить.
Во втором примере Чарли получает бесплатное счастье в первом месяце.
В третьем примере для Чарли оптимально купить счастье во втором месяце. Даже оставшись с деньгами в конце, Чарли не сможет вернуться назад во времени, чтобы получить предлагаемое счастье в первом месяце.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
1 10
1 5
2 80
0 10
200 100
3 100
70 100
100 200
150 150
5 8
3 1
5 3
3 4
1 5
5 3
2 5
1 5
2 1
5 3
2 5
2 4
4 1
5 1
3 4
5 2
2 1
1 2
3 5
3 2
3 2
|
0
10
200
15
1
9
9
|