cetatuie

După o seară reușită pe Piezișă, eroul nostru Alex ar trebui să se întoarcă acasă ... ar trebui. Însă, acesta nu dorește ca distracția să se termine, și decide sa viziteze un alt obiectiv turistic specific orășelului Jluc: Cetățuia.

Cetățuia poate fi văzută ca un șir de N dealuri, al i-lea deal având înălțimea $V_{i−1}$. După ce a cumpărat(și băut) mult lapte de la magazinele de pe Piezișă, Alex a observat ca are puteri supranaturale. Mai exact, el poate să crească înălțimea unui deal cu exact 1 unitate. Totuși, laptele începe să își piardă din efect, așa că el poate face asta de maxim K ori. Lui Alex nu îi place să urce sau să coboare mai mult decât este necesar, așadar, el își dorește să minimizeze suma $|V_0 - V_1|+|V_1 - V_2|+. . .+|V_{N−2} −V_{N−1}|$. Totuși, laptele de pe Piezișă are și un efect advers: îl face pe cel care l-a băut să gândească mai lent. Așadar, Alex va roagă pe voi să aflați valoarea minimă a sumei descrise mai sus, după aplicarea a maxim K operații.

Date de intrare

Pe prima linie se va găsi T, numărul de scenarii. Urmează apoi T grupe de câte 2 linii, fiecare descriind câte un scenariu de rezolvat. Pe prima linie a unui scenariu se găsesc N și K cu semnificația din enunț. Pe următoarea linie găsesc cele N elementele șirului V separate prin spații, unde al i-lea dintre ele reprezentând înălțimea celui de al i-lea deal.

Date de ieșire

Pentru fiecare scenariu se va afișa pe câte o linie gradul de dificultate minim care poate fi obținut.

Restricţii

• Gradul de dificultate al unui șir cu un singur element se consideră 0.
• 1 ≤ N ≤ 1 000 000
• $0 ≤ K ≤ 10^{18}$
• $1 ≤ V_i ≤ 10^9$
• suma N-urilor pentru toate scenariile este ≤ 1 000 000

Subtask 1 (5 puncte)

• $N ≤ 15, 1 ≤ V_i ≤ 40, K ≤ 10$, suma N-urilor ≤ 50

Subtask 2 (25 puncte)

• $N ≤ 100, 1 ≤ V_i ≤ 40,K ≤ 200$, suma N-urilor ≤ 500

Subtask 3 (10 puncte)

• N ≤ 1 000, suma N-urilor ≤ 10 000

Subtask 4 (15 puncte)

• $V_0 = V_{N−1} = 10^9$

Subtask 5 (20 puncte)

• N ≤ 100 000, suma N-urilor ≤ 100 000

Subtask 6 (25 puncte)

• Fără restricții adiționale.

Exemple

stdin

2
6 2
6 3 3 3 4 3
6 3
6 3 3 3 4 3

stdout

4
3

Explicații

Avem 2 scenarii. În ambele cazuri, șirul inițial de înălțimi este V = [6, 3, 3, 3, 4, 3].

În primul caz, K = 2, Alex va crește înălțimea ultimului deal o dată, iar astfel șirul final devine [6, 3, 3, 3, 4, 4].
Gradul de dificultate pe acest șir este: |6 − 3| + |3 − 3| + |3 − 3| + |3 − 4| + |4 − 4| = |3| + |0| + |0| + | − 1| + |0| = 3 + 1 = 4

În ultimul caz, K = 3, Alex va crește înălțimea fiecărui deal de pe pozițiile 1, 2 și 3 o singură dată. Astfel, șirul final devine [6, 4, 4, 4, 4, 3].
Gradul de dificultate pe acest șir este: |6 − 4| + |4 − 4| + |4 − 4| + |4 − 4| + |4 − 3| = |2| + |0| + |0| + |0| + |1| = 2 + 1 = 3