A. Прогулка по аллее
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы прогуливаетесь по аллее, находящейся недалеко от вашего дома. На аллее в ряд стоит $$$n+1$$$ лавочек, пронумерованных от $$$1$$$ до $$$n+1$$$ слева направо. Дистанция между лавочками $$$i$$$ и $$$i+1$$$ равна $$$a_i$$$ метров.

Изначально у вас есть $$$m$$$ единиц энергии. Для того чтобы пройти $$$1$$$ метр дистанции, вы тратите $$$1$$$ единицу энергии. Вы не можете идти, если у вас нет энергии. Также вы можете восстанавливать вашу энергию, когда сидите на лавочках (и это единственный способ восстановить энергию). Когда вы сидите, вы восстанавливаете любое целое количество энергии, которое хотите (если вы сидите дольше, вы восстанавливаете больше энергии). Заметьте, что количество вашей энергии может превышать $$$m$$$.

Ваша задача — найти минимальное количество энергии, которое вам необходимо восстановить (сидя на лавочках) для того, чтобы достичь лавочки $$$n+1$$$, начиная у лавочки $$$1$$$ (и закончить вашу прогулку).

Вам необходимо ответить на $$$t$$$ независимых наборов тестовых данных.

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

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.

Первая строка набора тестовых данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 100$$$; $$$1 \le m \le 10^4$$$).

Вторая строка набора тестовых данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 100$$$), где $$$a_i$$$ равно дистанции между лавочками $$$i$$$ и $$$i+1$$$.

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

Для каждого набора тестовых данных выведите одно целое число — минимальное количество энергии, которое вам необходимо восстановить (сидя на лавочках) для того, чтобы достичь лавочки $$$n+1$$$, начиная у лавочки $$$1$$$ (и закончить вашу прогулку) в соответствующем наборе тестовых данных.

Пример
Входные данные
3
3 1
1 2 1
4 5
3 3 5 2
5 16
1 2 3 4 5
Выходные данные
3
8
0
Примечание

В первом наборе тестовых данных примера вы можете дойти до лавочки $$$2$$$, потратив $$$1$$$ единицу энергии, затем восстановить $$$2$$$ единицы энергии на второй лавочке, дойти до лавочки $$$3$$$, потратив $$$2$$$ единицы энергии, восстановить $$$1$$$ единицу энергии и дойти до лавочки $$$4$$$.

В третьем наборе тестовых данных примера у вас уже достаточно энергии для того, чтобы дойти до лавочки $$$6$$$, не отдыхая на лавочках вообще.