Phileas Fogg and Passepartout are now going on a road trip in their brand new car. They start at location A₀ and need to go to A_N. Their car has a capacity to hold only C units of fuel and can travel unit distance on unit amount of fuel. They start by filling some amount of fuel from the filling station at A₀. On the way, there are several filling stations A₁, A₂,... A_N-1. The cost of fuel is not the same at all filling stations. Find the minimum amount that they have to spend on fuel to make the journey. Note that it is assured that the journey can be completed with the car of the given capacity.

Input

The first line of input contains T (≤10), the number of test cases. Following this are the descriptions of the testcases

The first line in the description of each test case contains two space integers N (≤50000) and C (≤10⁸). This is followed by N lines, each containing an integer. The integer on the ith line is the distance from A₀ to A_i and is ≤ 10⁸. The distances are in increasing order. This is followed by N more lines, each containing an integer. The integer on the ith line is the cost of one unit of fuel at the filling station A_i-1 and is ≤ 10⁸.

Output

Output one integer per test case, the minimum total amount that needs to be spent on fuel to complete the journey

Example

Input:
2
5 10
10
20
30
40
50
1
2
1
2
1
5 15
10
20
30
40
50
1
2
1
2
1
Output:
70
60