E. Деньги покупают счастье
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Будучи физиком, Чарли любит планировать свою жизнь в простых и точных терминах.

В течение следующих $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число, максимальную сумму счастья, которую мог бы получить Чарли.

Пример
Входные данные
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
Примечание

В первом примере Чарли получает зарплату только в конце месяца, поэтому не может позволить себе ничего купить.

Во втором примере Чарли получает бесплатное счастье в первом месяце.

В третьем примере для Чарли оптимально купить счастье во втором месяце. Даже оставшись с деньгами в конце, Чарли не сможет вернуться назад во времени, чтобы получить предлагаемое счастье в первом месяце.