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

h2. Date de intrare