Fişierul intrare/ieşire:	bisuma.in, bisuma.out	Sursă	Algoritmiada 2019 Runda Finala
Autor	Tamio-Vesa Nakajima	Adăugată de	Tamio Vesa Nakajima •tamionv
Timp execuţie pe test	1.5 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Bisuma

In metropola B., precum in toate metropolele, exista doua licee foarte tari, dar care sunt intr-o crunta rivalitate: Colegiul National X, si Liceul Teoretic Y. Acum, pentru ca in metropola conflictele se rezolva in mod civilizat, ei vor avea o competitie intelectuala pentru a vedea care liceu este mai tare. Pentru inceput, cate N elevi din fiecare liceu se alineaza, primul elev al CNX punandu-se langa primul elev din LTY, al doilea elev al CNX punandu-se langa cel de-al doilea elev din LTY, si asa mai departe. Fiecare elev are, desigur, o valoare. Competitia consta in a imparti sirul in K secvente continue. In fiecare secventa, copiii din fiecare liceu formeaza cate o echipa, si incep un duel al valorii. Castiga echipa cu valoarea totala mai mare. Apoi, valoarea intregii impartiri in bucati se considera a fi suma valorilor echipelor castigatoare a duelurilor din cele K subsecvente. Scopul competitiei este sa minimizam valoarea intregii impartiri in bucati.
Tu doresti sa aflii cea mai putin valoroasa impartire si sa folosesti aceasta informatie pentru a deveni conducatorul amanduora licee. Daca reusesti, fiecare liceu iti va da cate 50 de puncte pentru un 100 frumos :)

Mai formal, se da un sir de N perechi, si se cere impartirea acestuia in K subsecvente. Se considera valoarea unei subsecvente de perechi ca fiind egala cu maximul dintre suma primelor elemente din fiecare pereche si suma celorlalte elemente din perechi (mai exact, pentru subsecventa (a, b), ..., (x, y), se ia ca fiind max(a + ... + x, b + ... + y)). Dorim sa impartim sirul in cate K subsecvente, astfel incat valoarea impartirii sa fie minima.

Date de intrare

Fişierul de intrare bisuma.in va contine, pe o linie, numerele N si K. Pe cea de a doua linie se vor gasi valorile celor N elevi din Colegiul National X (adica, formal, primele componente ale perechilor din input), si pe cea de a treia linie, se vor gasi valorile celor N elevi din Liceul Teoretic Y (adica, formal, cele de a doua componente ale perechilor din input).

Date de ieşire

În fişierul de ieşire bisuma.out se va afisa valoarea totala cautata.

Restricţii

• 1 ≤ N ≤ 100.000
• 1 ≤ K ≤ min(N, 10)
• Oricare valoare nu depaseste 1.000.000.000 (niciun elev nu ar putea sa aibe o valoare mai mare ca a unui miliardar).
• Pentru 10 puncte, N ≤ 100.
• Pentru alte 20 de puncte, N ≤ 1000.'
• Fiecare test din feedback face parte din alta grupa de teste; primul test are N ≤ 100, al doilea test are N ≤ 1000, iar restul au N ≤ 100.000.

Exemplu

Explicatie

Se imparte sirul in doua subsecvente, una de un element (de valoare 5), si una de patru elemente (de valoare 14).

Cum se trimit solutii?