optimize-2

We model a stock price with the following function: $$f(x)=A_1|B_1-x| + \ldots + A_N|B_N-x|$$ Currently we are at time $x=1$. We want to know: given a time interval $[1,M]$, what is the maximum profit ($P$) we can achieve by buying and then selling the stock. We can use any times $1 ≤ x ≤ y ≤ M$ for buying ($x$) and selling ($y$). If we don’t buy/sell anything, our profit is $0$ of course.

Input specification

All data are integers. In the first line comes $T$ the number of test cases. Description of each test case: First line contains $N$ and $M$. Next line contains $A_1,\ldots,A_N$. Third line contains $B_1,\ldots,B_N$, which are distinct values.

Output specification

$T$ lines, each containing the requested number $P$.

Constraints

$1\le T \le 100$
$1\le N \le 100$
$1\le M \le 1\_000\_000\_000$
$1\le A_k \le 100$
$1\le B_k \le 1\_000\_000\_000$

Sample input 1

1. 5
2. 4 10
3. 1 2 3 4
4. 1 2 3 4
5. 9 10
6. 1 2 3 1 2 3 1 2 3
7. 1 2 4 8 16 32 64 128 256
8. 9 50
9. 1 2 3 1 2 3 1 2 3
10. 1 2 4 8 16 32 64 128 256
11. 9 100
12. 1 2 3 1 2 3 1 2 3
13. 1 2 4 8 16 32 64 128 256
14. 9 300
15. 1 2 3 1 2 3 1 2 3
16. 1 2 4 8 16 32 64 128 256

Sample output 1

1. 62
2. 0
3. 108
4. 480
5. 3032