Young Barry is busy with his video game since the morning. He is trying hard to win the game but is failing each time. The game is about saving a city from an alien invasion. All the citizens have been taken hostage by the aliens. The citizens have been held imprisoned in a number of peculiar vessels guarded by a sleeping alien.

In order to save their lives, the player can either kill the alien or quietly bring out all the people in that vessel to safety. The more the number of people can the player bring out, more does the chance of winning the game increases. The player initially starts with some energy units. However, moving from one vessel to another results in the consumption of 1 energy unit. Killing an alien results in the gaining of some energy units. However, killing an alien won’t increase the number of people rescued. It would only help him gain some energy. Now, moving from vessel to vessel, he can either kill an alien or rescue people but can’t do both or none. The energy level cannot drop beyond 0.

Taking the number of vessels to be m, the player can move only in the forward direction (i.e. from vessel 1 to vessel 2 and then to vessel 3, etc…). The player starts his rescue mission from the invader’s base camp and moving from the base camp to vessel 1 also results in the consumption of an energy unit. Now, what is the maximum number of people that Barry needs to rescue in order to win the game?

Input Format:

The first line contains the total number of test cases (t).

The second line contains two integers m and n denoting the total number of vessels and the initial number of energy units that a player starts his game with.

The third line contains m space separated integers, where each integer (alien[k]) denotes the number of energy units that can be gained by killing the alien guarding the kth vessel.

The fourth line contains m space separated integers, where each integer (people[k]) denotes the number of people being held captive in the kth vessel.

Output format:

For each test case, output the maximum number of people that Barry needs to rescue in order to win the game .

Constraints:

1<=t<=100

1<=m<=1000

0<=n<=10^18

0<=alien[k]<=1000

0<=people[k]<=1000

Example:

Sample Input:

1

3 2

1 2 1

100 1 100

Sample Output:

200