Cerința
Înștiințat de atacul orcilor, Gandalf și-a luat măsurile de precauție. Credinciosul spion i-a adus acestuia o hartă care arată pozițiile celor n
orci. Harta poate fi reprezentată ca un sistem cartezian de coordonate. Gandalf vrea să folosească o vrajă astfel încât să anihileze cel puțin k
orci. De asemenea, acesta vrea să folosească cât mai puțină mana. Știind că, dacă utilizează r
mana (r
număr natural), și vraja este folosită în punctul de coordonate (x,y)
, acesta anihilează toți orcii din interiorul cercului cu centrul în (x,y)
de rază r
, aflați mana minimă necesară pentru a anihila k
orci.
Date de intrare
Fișierul de intrare mana.in
conține pe prima linie două numere naturale n
, k
, cu semnificațiile din enunț. Pe următoarele n
linii se găsesc câte două numere întregi separate printr-un spațiu, reprezentând abscisa respectiv ordonata fiecărui orc de pe hartă.
Date de ieșire
Fișierul de ieșire mana.out
va conține pe prima linie numărul r
, reprezentând mana minimă pe care o poate utiliza Gandalf pentru a anihila k
orci.
Restricții și precizări
1 ≤ k ≤ n ≤ 100
- Numerele din fișierul de intrare sunt întregi cuprinse între
-100000
și100000
.
Exemplu:
mana.in
5 3 3 3 5 3 1 -5 -4 1 0 3
mana.out
3
Explicație
Gandalf poate să folosească vraja în punctul de abscisă 2,5
și ordonată 3
.