split2

Split2

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

Se da un sir 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.

Se da un sir $V$ cu $N$ numere naturale. Se doreste impartirea acestuia in $M$ subsecvente de lungime para. Costul unei subsecvente este egal cu maximul dintre suma elementelor din prima jumatate 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 minim al unei impartiri.

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

h2. Date de intrare

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

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 ale sirului $V$.

h2. Date de ieşire

În fişierul de ieşire $split2.out$ ...

În fişierul de ieşire $split2.out$ se va scrie pe cate o linie rezultatul cerut pentru fiecare din cele T teste.

h2. Restricţii

* $1 ≤ M ≤ N &le 1000$

* $1 ≤ T ≤ 50$
* $1 ≤ M ≤ N ≤ 1000$
* $1 ≤ V[i] ≤ 10000$
* $N este par.$
* Se garanteaza ca exista o impartire in M intervale

h2. Exemplu
table(example). |_. split2.in |_. split2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 1
10 3
1 2 4 2 4 5 2 2 1 3
| 6

|
h3. Explicaţie

...

1 2 4 2 | 4 5 | 2 2 1 3

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

Prima subsecventa 1 2 4 2 are costul 6.
A doua subsecventa 4 5 are costul 5.
A treia subsecventa 2 2 1 3 are costul 4.
 
== include(page="template/taskfooter" task_id="split2") ==

9414