Codeforces Round 946 (Div. 3) |
---|
Закончено |
Будучи физиком, Чарли любит планировать свою жизнь в простых и точных терминах.
В течение следующих $$$m$$$ месяцев, начиная с нулевой суммы денег, Чарли будет усердно работать и зарабатывать $$$x$$$ фунтов в месяц. Для $$$i$$$-го месяца $$$(1 \le i \le m)$$$ будет одна возможность потратить сумму $$$c_i$$$ фунтов, чтобы получить счастье $$$h_i$$$.
Запрещено брать в долг. Заработанные деньги в $$$i$$$-м месяце можно тратить только в более поздний месяц $$$j$$$ ($$$j>i$$$).
Поскольку физики не пишут код, помогите Чарли найти максимально возможную сумму счастья.
Первая строка ввода содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.
Первая строка каждого набора содержит два целых числа, $$$m$$$ и $$$x$$$ ($$$1 \le m \le 50$$$, $$$1 \le x \le 10^8$$$) — общее количество месяцев и ежемесячная зарплата.
$$$i$$$-я из следующих $$$m$$$ строк содержит два целых числа, $$$c_i$$$ и $$$h_i$$$ ($$$0 \le c_i \le 10^8$$$, $$$1 \le h_i \le 10^3$$$) — стоимость и предлагаемое счастье за $$$i$$$-й месяц. Обратите внимание, что иногда счастье может быть бесплатным ($$$c_i=0$$$ для некоторых $$$i$$$).
Гарантируется, что сумма $$$\sum_i h_i$$$ по всем наборам входных данных не превышает $$$10^5$$$.
Для каждого набора входных данных выведите одно целое число, максимальную сумму счастья, которую мог бы получить Чарли.
71 101 52 800 10200 1003 10070 100100 200150 1505 83 15 33 41 55 32 51 52 15 32 52 44 15 13 45 22 11 23 53 23 2
0 10 200 15 1 9 9
В первом примере Чарли получает зарплату только в конце месяца, поэтому не может позволить себе ничего купить.
Во втором примере Чарли получает бесплатное счастье в первом месяце.
В третьем примере для Чарли оптимально купить счастье во втором месяце. Даже оставшись с деньгами в конце, Чарли не сможет вернуться назад во времени, чтобы получить предлагаемое счастье в первом месяце.
Название |
---|