The meteorological service of Nlogonia forecast for the next months the worst drought in Nlogonia’s history. This is why his mayor has decided to install the largest tank in the history of the planet, to maintain water supplies to enable them to face the crisis. a) Frontal view of the tank. b) Aereal view of the tank (Dotted lines are submerged walls) The tank is a big box, with n consecutive compartments as you can see in the previous picture. The walls of some compartments may be completely submerged. The mayor wants to know how many cubic centimeters of water will fit in the tank before filling it, since he does not want a single drop to be spilled. Can you help him? Note that the front and back walls (not visible in the drawing) are high enough so the water never reaches its upper limit, so if a drop spills, it will spill over the wall at height h0 or hn. Similarly, the walls were built in a super thin material, so its volume is negligible and you can ignore it. Input The first line of the input contains an integer T, the number of test cases. Each case begins with a line with two integers a and n, separated by spaces. The next line has n integers x1 , x2 , . . . , xn , separated by spaces, the distance of each intern wall of the tank to the previous wall (the width of each compartment). The last line of each test case has n + 1 integers h0, h1, . . . , hn separated by spaces, the height of every intern wall. All the measures are given in meters (1 ≤ a, n, xi, hi ≤ 104). Output Print one line per test case, an integer with the maximum capacity of the tank in cubic meters. It is guaranteed that this number fits in a 64 bits signed integer. Sample Input 1 10 6 10 6 6 8 8 7 20 24 8 18 18 12 15 Sample Output 7850