== include(page="template/taskheader" task_id="split2") ==

Se da un sir $V$ de $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 secvente.

Se da un sir $V$ de $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. Costul total al unei impartiri este egal cu costul maxim al unei secvente.

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

Sa se calculeze costul minim al unei impartiri.

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 doua numere: N si M. Pe cea de a doua linie se afla cele N numere intregi ale sirului V

Fişierul de intrare $split2.in$ ...

h2. Date de ieşire