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 a fi cunoscute distanta intre 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 + 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") ==