A. Gym Tournament
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

After the last tournament that Yaman participated in, he gained some experience that he will use in the next tournament.

The gym in which he exercises has $$$n$$$ barbell plates numbered from $$$1$$$ to $$$n$$$, and the weight of the $$$i$$$-th plate is $$$a_i$$$ and its width is $$$b_i$$$.

Yaman will train on an exercise that uses a bar with two sides, so he will choose two disjoint subsets from the $$$n$$$ plates, one for each side.

Yaman's coach has a balancing function $$$f$$$ that takes the subset of each side and returns the balancing value.

Assuming that the left side subset is $$$l$$$ and it contains $$$cnt_l$$$ numbers $$$[l_1, l_2, .., l_{cnt_l}]$$$ which represent the indices of the left side subset, and the right side subset is $$$r$$$ and it contains $$$cnt_r$$$ numbers $$$[r_1, r_2, .., r_{cnt_r}]$$$ which represent the indices of the right side subset, then the function $$$f$$$ is:

$$$$$$f(l, r) = | ( \sum_{i = 1}^{cnt_l}(b_{l_i}) - \sum_{i = 1}^{cnt_r} (b_{r_i}) ) |$$$$$$

The coach wants to test Yaman on $$$q$$$ tests, each one has two numbers $$$L$$$, $$$R$$$, and he wants to know the maximum total weight of both sides that Yaman can lift if the value of the balancing function $$$f$$$ is between $$$[L, R]$$$ inclusive.

Help Yaman's coach to determine the maximum weight for each test or print $$$0$$$ if he can't achieve the wanted balancing value.

Input

The first line contains the number of test cases $$$t$$$ $$$( 1 \le t \le 10^{5} )$$$. A description of the test cases follows.

The first line of each test case contains two integers $$$n$$$, $$$q$$$ $$$( 1 \le n \le 10^{5} )$$$, $$$( 1 \le q \le 10^{6} )$$$ — the number of barbell plates in the gym, and the number of tests respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, .., a_n$$$ $$$( 1 \le a_i \le 10^{9} )$$$ — the weights of the barbell plates.

The third line contains $$$n$$$ integers $$$b_1, b_2, .., b_n$$$ $$$( 1 \le b_i \le 10^{5} )$$$ — the width of the barbell plates.

The next $$$q$$$ lines contain two integers $$$L_i$$$, $$$R_i$$$ $$$( 1 \le L_i \le R_i \le 10^{5} )$$$ — the range of the value of the balancing function in the $$$i$$$-th test.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^{5}$$$.

And it is guaranteed that the sum of $$$b_i$$$ over all test cases does not exceed $$$10^{5}$$$.

And it is guaranteed that the sum of $$$q$$$ over all test cases does not exceed $$$10^{6}$$$.

Output

Print the maximum weight for each test or print $$$0$$$ if he can't achieve the wanted balancing value.

Example
Input
1
5 4
5 2 3 2 5
1 4 9 12 20
1 2
7 7
99 100
3 3
Output
17
12
0
14