A. Parkway Walk

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are walking through a parkway near your house. The parkway has n+1n+1 benches in a row numbered from 11 to n+1n+1 from left to right. The distance between the bench ii and i+1i+1 is aiai meters.

Initially, you have mm units of energy. To walk 11 meter of distance, you spend 11 unit of your energy. You can't walk if you have no energy. Also, you can restore your energy by sitting on benches (and this is the only way to restore the energy). When you are sitting, you can restore any integer amount of energy you want (if you sit longer, you restore more energy). Note that the amount of your energy can exceed mm.

Your task is to find the minimum amount of energy you have to restore (by sitting on benches) to reach the bench n+1n+1 from the bench 11 (and end your walk).

You have to answer tt independent test cases.

Input

The first line of the input contains one integer tt (1≤t≤1001≤t≤100) — the number of test cases. Then tt test cases follow.

The first line of the test case contains two integers nn and mm (1≤n≤1001≤n≤100; 1≤m≤1041≤m≤104).

The second line of the test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1001≤ai≤100), where aiai is the distance between benches ii and i+1i+1.

Output

For each test case, print one integer — the minimum amount of energy you have to restore (by sitting on benches) to reach the bench n+1n+1 from the bench 11 (and end your walk) in the corresponding test case.

Example

input

Copy

3
3 1
1 2 1
4 5
3 3 5 2
5 16
1 2 3 4 5

output

Copy

3
8
0

Note

In the first test case of the example, you can walk to the bench 22, spending 11 unit of energy, then restore 22 units of energy on the second bench, walk to the bench 33, spending 22 units of energy, restore 11 unit of energy and go to the bench 44.

In the third test case of the example, you have enough energy to just go to the bench 66 without sitting at all.

Problem solving instructions ： Water problem , After direct accumulation, subtract the original value , If it is larger than, you need to supplement energy , Otherwise, there is no need to supplement .

#include<stdio.h>
int main()
{
	int x;
	scanf("%d", &x);
	while (x--)
	{
		int y, z, p, sum = 0;
		scanf("%d%d", &y, &z);
		for (int i = 0; i<y; i++)
		{
			scanf("%d", &p);
			sum = sum + p;
		}
		if (sum > z)
		{
			printf("%d\n", sum - z);
		}
		else
		{
			printf("0\n");
		}
	}
	return 0;
}