Se da un sir $V$ cu $N$ numere intregi. Se doreste impartirea acestuia in $M$ subsecvente de lungime para. Costul unei subsecvente este egal cu maximul dintre suma elementelor din prima jumate si suma celor din a doua jumatate a subsecventei. Costul total al unei impartiri este egal cu costul maxim al unei subsecvente.

Sa se calculeze costul total minim care poate fi optinut prin impartirea sirului $V$.

Sa se calculeze costul total minim care poate fi optinut prin impartirea sirului V.

h2. Date de intrare

Fişierul de intrare $split2.in$ contine pe prima linie $T$, numarul de teste. In continuare, fiecare test contine 2 linii. Pe prima din ele se afla $N$ si $M$. Pe cea de a doua linie se afla cele $N$ numere intregi ale sirului $V$.

Fişierul de intrare $split2.in$ contine pe prima linie T, numarul de teste. In continuare, fiecare test contine 2 linii. Pe prima din ele se afla doua numere: N si M. Pe cea de a doua linie se afla cele N numere intregi ale sirului V.

h2. Date de ieşire