Вы прогуливаетесь по аллее, находящейся недалеко от вашего дома. На аллее в ряд стоит \(n+1\) лавочек, пронумерованных от \(1\) до \(n+1\) слева направо. Дистанция между лавочками \(i\) и \(i+1\) равна \(a_i\) метров.
Изначально у вас есть \(m\) единиц энергии. Для того чтобы пройти \(1\) метр дистанции, вы тратите \(1\) единицу энергии. Вы не можете идти, если у вас нет энергии. Также вы можете восстанавливать вашу энергию, когда сидите на лавочках (и это единственный способ восстановить энергию). Когда вы сидите, вы восстанавливаете любое целое количество энергии, которое хотите (если вы сидите дольше, вы восстанавливаете больше энергии). Заметьте, что количество вашей энергии может превышать \(m\).
Ваша задача — найти минимальное количество энергии, которое вам необходимо восстановить (сидя на лавочках) для того, чтобы достичь лавочки \(n+1\), начиная у лавочки \(1\) (и закончить вашу прогулку).
Вам необходимо ответить на \(t\) независимых наборов тестовых данных.
Выходные данные
Для каждого набора тестовых данных выведите одно целое число — минимальное количество энергии, которое вам необходимо восстановить (сидя на лавочках) для того, чтобы достичь лавочки \(n+1\), начиная у лавочки \(1\) (и закончить вашу прогулку) в соответствующем наборе тестовых данных.
Примечание
В первом наборе тестовых данных примера вы можете дойти до лавочки \(2\), потратив \(1\) единицу энергии, затем восстановить \(2\) единицы энергии на второй лавочке, дойти до лавочки \(3\), потратив \(2\) единицы энергии, восстановить \(1\) единицу энергии и дойти до лавочки \(4\).
В третьем наборе тестовых данных примера у вас уже достаточно энергии для того, чтобы дойти до лавочки \(6\), не отдыхая на лавочках вообще.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 1
1 2 1
4 5
3 3 5 2
5 16
1 2 3 4 5
|
3
8
0
|