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 al unui coechipier in a isi realiza home-run-ul sa fie minim.

h2. Date de intrare

* $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.

h2. Exemplu