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

Tokuchi Toua are un nou meci de baseball pe care trebuie sa il castige. Putem considera ca terenul de baseball este un poligon cu $N$ varfuri in plan iar Toua (pitcherul) se afla intr-un punct din poligon. Toua poate sa pozitioneze un coechipier in unul din cele $N$ puncte. In momentul in care coechipierul primeste mingea, acesta incepe sa alerge pentru a realiza un home-run (incepe sa alerge de-alungul perimetrului poligonului pana ajunge in punctul altui coechipier).

Tokuchi Toua are un nou meci de baseball pe care trebuie sa il castige. Putem considera ca terenul de baseball este un poligon cu $N$ varfuri in plan iar Toua (pitcherul) se afla intr-un punct din interiorul poligonului. Toua poate sa pozitioneze un coechipier in unul din cele $N$ puncte. In momentul in care coechipierul primeste mingea, acesta incepe sa alerge pentru a realiza un home-run (incepe sa alerge de-alungul perimetrului poligonului pana ajunge in punctul altui coechipier). Scopul este sa pozitionam unul sau mai multi coechipieri astfel incat acestia sa acopere tot perimetrul poligonului intr-un timp cat mai scurt.

Pentru simplitate, consideram ca cunoasteam distanta intre oricare doua puncte consecutive de pe poligon si timpul necesar pentru a arunca mingea in fiecare din cele $N$ puncte. Timpul necesar al unui coechipier pentru a isi termina home-run-ul este calculat in felul urmator: timpul pana primeste mingea de la pitcher + distanta pe care acesta o parcurge din punctul in care se afla pana in punctul urmatorului coechipier. Toua poate sa pozitioneze maxim $K$ coechipieri in $K$ din cele $N$ puncte. Voi trebuie sa il ajutati sa realizeze acest lucru astfel incat timpul maxim al unui coechipier in a isi realiza home-run-ul sa fie minim.

Pentru simplitate, consideram a fi cunoscute duratele de parcurgere ale muchiilor între oricare doua puncte consecutive de pe poligon, precum si timpul necesar pentru a arunca mingea in fiecare din cele $N$ puncte. Timpul necesar al unui coechipier pentru a isi termina home-run-ul este calculat in felul urmator: timpul pana primeste mingea de la pitcher + timpul pe care acesta il parcurge din punctul in care se afla pana in punctul urmatorului coechipier. Toua poate sa pozitioneze maxim $K$ coechipieri in $K$ din cele $N$ puncte. Voi trebuie sa il ajutati sa realizeze acest lucru astfel incat timpul maxim necesar al unui coechipier pentru a isi realiza home-run-ul sa fie minim.

h2. Date de intrare

Fişierul de intrare $oneouts.in$ pe prima linie $2$ numere naturale $N$ si $K$. Pe urmatoarea linie vor fi $N$ numere naturale reprezentand distanta intre oricare $2$ puncte consecutive de pe poligon (punctul $1$ cu $2$, $2$ cu $3$, .... , $N$ cu $1$). Pe linia $3$ vor fi alte $N$ numere naturale, al $i$-lea reprezentand timpul necesar pentru ca Toua sa arunde mingea din punctul in care se afla pana in punctul cu indicele $i$ de pe poligon

Fişierul de intrare $oneouts.in$ pe prima linie $2$ numere naturale $N$ si $K$. Pe urmatoarea linie vor fi $N$ numere naturale reprezentand timpul de parcurgere al distantei intre oricare $2$ puncte consecutive de pe poligon (punctul $1$ cu $2$, $2$ cu $3$, .... , $N$ cu $1$). Pe linia $3$ vor fi alte $N$ numere naturale, al $i$-lea reprezentand timpul necesar pentru ca Toua sa arunde mingea din punctul in care se afla pana in punctul cu indicele $i$ de pe poligon

h2. Date de ieşire

* $1 &le; K <= N &le; 100.000$
* Toate valorile din input sunt din intervalul $[1, 1.000.000.000]$

* Poligonul menţionat în enunţ este fictiv. În general nu există nicio relaţie geometrică între timpii descrişi în fişierul de intrare.
* Cand coechipierii isi alearga home-run-ul ei trebuie sa se deplaseze spre dreapta, astfel daca ei sa afla la un moment in punctul $N$, atunci ei se vor deplasa in directia punctului $1$, iar daca se afla intr-un alt punct $i$ se vor deplasa in directia punctului $i+1$.
* Pentru teste in valoare de *20%* din punctaj $N ≤ 20$, iar toate celelalte valori din input sunt din intervalul $[1, 10.000]$.
* Pentru teste in valoare de *40%* din punctaj $N ≤ 1500$.

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

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

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

|
h3. Explicaţie

...

Toua isi va amplasa cei $2$ coechipieri in varfurile $1$ si $3$. Coechipierul din varful $1$ isi va executa home-run-ul in $3(timpul necesar pentru ca Toua sa-i arunce lui mingea) + 3 + 1(timpul necesar sa alerge pana la pozitia celuilalt coechipier) = 7$. Coechipierul din varful $3$ isi va executa home-run-ul in $1(timpul pana va ajunge mingea la el) + 2 + 3 + 2 = 8$.

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