optimize-2

Egy reszvény árfolyamát a következő függvénnyel modellezzük: $$f(x)=A_1|B_1-x| + \ldots + A_N|B_N-x|$$ Most az $x=1$ időpontban vagyunk. Arra vagyunk kíváncsiak hogy adott $[1,M]$ időintervallum esetén mekkora a legnagyobb nyereség ($P$) amit el tudunk érni egy részvény vásárlásával majd eladásával. Bármilyen $1\le x \le y\le M$ időpontokat használhatunk a vásárlásra ($x$) illetve eladásra ($y$). Ha nem vásárlunk/adunk el semmit akkor a hasznunk $0$ természetesen.

Bemenet specifikáció

Minden adat egész szám. Az első sorban van $T$ az esetek száma. Egy eset leírása: Az első sor az $N$-et és az $M$-et tartalmazza. A következő sorban az $A_1,\ldots,A_N$ mennyiségek. A harmadikban pedig a $B_1,\ldots,B_N$ mennyiségek, melyek különböző értékek.

Kimenet specifikáció

$T$ sor, mindegyikben a keresett $P$ szám.

Korlátok

$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$

1. példa bemenet

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

1. példa kimenet

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