TVA++

În Regatul Finanțelor fiecare companie este evaluată printr-o listă de profituri anuale.
Ministerul Valorilor Adăugate (MVA) dorește să afle cât de „sănătoasă” este o firmă măsurând cea mai mare sumă ce poate fi obținută dintr-o creștere constantă a profitului, aceasta numindu-se valoarea firmei.

Din când în când, inspectorii efectuează o transformare fiscală: rapoartele companiei sunt răsturnate, prima lună schimbând locul cu ultima, a doua cu penultima și așa mai departe.

După fiecare astfel de transformare, se recalculează valoarea firmei.
Ministerul dorește să știe care este valoarea totală ($ANS$) după aplicarea acestor verificări succesive de un număr dat de ori.

Cerință

Se dă o secvență de $N$ numere naturale $A[1], A[2], \ldots, A[N]$ și un număr natural nenul $P$.
O subsecvență este $\left(A[j_{1}], A[j_{2}], \ldots, A[j_{k}]\right)$, cu $1\leq j_{1}<j_{2}<\ldots <j_{k}\leq N$. Spunem că o subsecvență este strict crescătoare dacă $A[j_{1}]<A[j_{2}]< \ldots < A[j_{k}]$.

Definim operația $\textit{TRANSFORMARE}(A)$, care interschimbă $A[i]$ cu $A[N-i+1]$, pentru fiecare $1\leq i\leq N / 2$.
Notăm valoarea unei secvențe cu $\textit{VALUE}(A)$, reprezentând valoarea maximă a sumei elementelor unei subsecvențe strict crescătoare din secvența $A$.

Construim șirul de șiruri $B$ astfel:

• $B[1]=A$;
• $B[i] =\textit{TRANSFORMARE}(B[i - 1])$, pentru $i>1$.

Definim $\textit{ANS}(A,P)$ astfel:

Cerința este să determinați $ANS(A,P)$.

Date de intrare

Fișierul de intrare tva++.in conține:

• pe prima linie două numere naturale nenule, $N$ și $P$, cu semnificația din enunț;
• pe următoarea linie $N$ numere naturale, reprezentând elementele secvenței $A$.

Date de ieșire

Se va afișa în fișierul de ieșire tva++.out valoarea lui $ANS(A,P)$.

Restricții și precizări

• $1\leq N\leq 200 \ 000$;
• $1\leq P\leq 1 \ 000 \ 000$;
• $1\leq A[i]\leq 100 \ 000$, $1\leq i\leq N$.

Exemplul 1

tva++.in

5 2 
1 2 3 4 5

tva++.out

10

Explicație

$ANS(A, P) = VALUE(B[1]) - VALUE(B[2]) = 15 - 5 = 10$

Exemplul 2

tva++.in

5 1 
1 2 3 4 5 

tva++.out

15 

Explicație

$ANS(A,P)=(+1)\cdot VALUE(B[1])=15$.

Exemplul 3

tva++.in

5 2
1 101 2 3 100

tva++.out

-95 

Explicație

$ANS(A,P)=(+1)\cdot VALUE(B[1])+(-1)\cdot VALUE(B[2])=106-201=-95$.

Exemplul 4

tva++.in

4 7
2 2 2 2

tva++.out

2

Explicație

$ANS(A,P)=2-2+2-2+2-2+2=2$.