E.Enerji kristalları

Laboratoriyada bir sırada düzülmüş $n$ ədəd enerji kristalı var. Soldan sağa $i$-ci kristalın tezlik növü $c_i$ ($1 \le c_i \le n$) və gücü $a_i$ ($1 \le a_i \le 10^9$) ilə ifadə olunur.

Bütün sıranı bir və ya bir neçə ardıcıl (kəsilməz) seqmentə bölməlisiniz. Seqmentlər $[l_1, r_1], [l_2, r_2], \dots, [l_m, r_m]$ şəklində olmalı və aşağıdakı şərtləri ödəməlidir:

• $l_1 = 1$ və $r_m = n$;
• $l_{j+1} = r_j + 1$ hər $1 \le j < m$ üçün.

Beləliklə, hər bir kristal dəqiq bir seqmentə daxil olur.

Bölgü aşağıdakı qaydaya tabe olmalıdır:

Tezlik təcridi: Eyni seqment daxilində eyni tezlikli iki kristal ola bilməz. Başqa sözlə, hər bir $[l, r]$ seqmentində $c_l, c_{l+1}, \dots, c_r$ qiymətləri cüt-cüt fərqli olmalıdır.

Hər bir $[l, r]$ seqmentinin xalis gücü həmin seqmentdəki ən güclü kristalın gücündən sabit $k$ izolyasiya xərcinin çıxılması ilə hesablanır:

$$\operatorname{val}(l,r)=\max_{l\le x\le r} a_x-k.$$

Bütün kristalları qaydalara uyğun seqmentlərə bölərək əldə edilə biləcək maksimum ümumi xalis gücü tapın:

$$\sum_{j=1}^{m}\operatorname{val}(l_j,r_j).$$

Cavab mənfi də ola bilər.

Giriş verilənləri

Birinci sətirdə testlərin sayı $t$ ($1 \le t \le 10^4$) verilir.

Hər testin birinci sətrində iki tam ədəd $n$ və $k$ ($1 \le n \le 2 \cdot 10^5$, $0 \le k \le 10^9$) verilir.

İkinci sətirdə $n$ tam ədəd $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$) verilir.

Üçüncü sətirdə $n$ tam ədəd $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) verilir.

Bütün testlər üzrə $n$-lərin cəmi $2 \cdot 10^5$-i aşmır.

Çıxış verilənləri

Hər test üçün yeni sətirdə əldə edilə biləcək maksimum ümumi xalis gücü çap edin.

Qeydlər

• Hər kristalı ayrıca seqmentə yerləşdirmək həmişə mümkündür, ona görə düzgün bölgü həmişə mövcuddur.
• Cavabın mütləq qiyməti $2 \cdot 10^{14}$-ü keçə bilər, ona görə 64 bitlik tam tipdən (məsələn, long long) istifadə edin.

Qiymətləndirmə

• Alt tapşırıq 1 — 20 bal: $n \le 10$.
• Alt tapşırıq 2 — 10 bal: $k = 0$.
• Alt tapşırıq 3 — 10 bal: hər test halında $c_1, c_2, \dots, c_n$ cüt-cüt fərqlidir.
• Alt tapşırıq 4 — 15 bal: hər test halında $a_1 = a_2 = \dots = a_n$.
• Alt tapşırıq 5 — 25 bal: $n \le 100$; bir test faylında $n$-lərin cəmi $\le 2000$.
• Alt tapşırıq 6 — 30 bal: $n \le 5000$; bir test faylında $n$-lərin cəmi $\le 5000$.
• Alt tapşırıq 7 — 25 bal: $c_i \le 10$.
• Alt tapşırıq 8 — 30 bal: $c_i \le 300$.
• Alt tapşırıq 9 — 30 bal: hər test halında $a$ ardıcıllığı ya azalmayandır ($a_1 \le a_2 \le \dots \le a_n$), ya da artmayandır ($a_1 \ge a_2 \ge \dots \ge a_n$).
• Alt tapşırıq 10 — 55 bal: əlavə məhdudiyyət yoxdur; əsas məhdudiyyətlər qüvvədədir.

Məsələ ümumilikdə 250 bal təşkil edir. Alt tapşırıq balları müstəqil test qrupları vasitəsilə hesablanır. Hər qrupun bütün testləri keçildikdə həmin qrupun balları verilir.

Izah

• Birinci test: Optimal bölgülərdən biri $[1, 2]$, $[3, 3]$, $[4, 4]$ və $[5, 6]$ seqmentlərindən ibarətdir. Onların xalis gücləri müvafiq olaraq $25 - 8 = 17$, $11 - 8 = 3$, $4 - 8 = -4$ və $13 - 8 = 5$ olur. Ümumi nəticə $17 + 3 - 4 + 5 = 21$-dir.
• İkinci test: $[1, 1]$, $[2, 2]$, $[3, 3]$ və $[4, 5]$ seqmentləri seçilə bilər. Onların xalis gücləri $10 - 3 = 7$, $4 - 3 = 1$, $15 - 3 = 12$ və $12 - 3 = 9$ olur. Ümumi nəticə $7 + 1 + 12 + 9 = 29$-dur.
• Üçüncü test: Bütün kristalların tezlik növü eyni olduğundan hər kristal ayrıca seqmentdə olmalıdır. Buna görə cavab $(5 - 10) + (20 - 10) + (1 - 10) + (100 - 10) = 86$ olur.

3
6 8
1 3 2 2 2 1
7 25 11 4 3 13
5 3
1 2 3 2 1
10 4 15 2 12
4 10
1 1 1 1
5 20 1 100

21
29
86