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

Poveste şi cerinţă...

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).
 
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.

h2. Date de intrare

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

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

h2. Date de ieşire

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

Fişierul de ieşire $oneouts.out$ va contine un singur numar natural reprezentand timpul minim cerut.

h2. Restricţii

* $... ≤ ... ≤ ...$

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

h2. Exemplu