Travel with candy

Problem Description

There are n+1 cities on a line. They are labeled from city 0 to city n. Mph has to start his travel from city 0, passing city 1,2,3...n-1 in order and finally arrive city n. The distance between city i and city 0 is $a_i$. Mph loves candies and when he travels one unit of distance, he should eat one unit of candy. Luckily, there are candy shops in the city and there are infinite candies in these shops. The price of buying and selling candies in city i is $buy_i$ and $sell_i$ per unit respectively. Mph can carry at most C unit of candies. Now, Mph want you to calculate the minimum cost in his travel plan.

Input

There are multiple test cases. The first line has a number T, representing the number of test cases. For each test : The first line contains two numbers $N$ and $C$ $(N \leq 2\times 10^5, C\leq 10^6)$ The second line contains $N$ numbers $a_1,a_2,...,a_n$. It is guaranteed that $a_i>a_{i-1}$ for each $1< i<=N$ . Next $N+1$ line : the i-th line contains two numbers $buy_{i-1}$ and $sell_{i-1}$ respectively. ($sell_{i-1} \leq buy_{i-1} \leq 10^6$) The sum of $N$ in each test is less than $3\times 10^5$.

Output

Each test case outputs a single number representing your answer.(Note: the answer can be a negative number)

Sample Input

1
4 9
6 7 13 18
10 7
8 4
3 2
5 4
5 4

Sample Output

105

Author

SXYZ

Source

2015 Multi-University Training Contest 8