Amicul nostru Vasile a devenit
foarte bogat si doreste sa deschida un lantisor de K
pizzerii, care sa primeasca si comenzi pentru acasa.
Vasile are în vedere M
potentiale locatii pentru pizzeriile sale. O pizzerie poate onora toate comenzile
din raza sa de actiune (o zona circulara de raza R,
cu centrul în locatia restaurantului).
Se stie ca studentii sunt mari consumatori de pizza, asa ca Vasile îi
considera clienti siguri. Din acest motiv Vasile a identificat locatiile a N
camine studentesti, precum si numarul de studenti din fiecare camin.
Vasile vrea sa aleaga K dintre
cele M locatii posibile pentru
pizzeriile sale, astfel încât numarul total de clienti siguri sa
fie cât mai mare posibil.
Cerinta
Scrieti un program care sa
determine numarul maxim de clienti siguri pe care Vasile se poate baza.
Date
de intrare
Prima linie a fisierului
de intrare pizza1.in contine doua
numere întregi K si R,
separate printr-un spatiu, reprezentând numarul de pizzerii pe care vrea
sa le deschida Vasile si respectiv raza de actiune a fiecarei pizzerii.
Pe cea de a doua linie se afla un numar natural M,
reprezentând numarul de locatii posibile pentru pizzerii.
Fiecare dintre urmatoarele M
linii contine doua numere întregi X
si Y, separate printr-un spatiu,
reprezentând coordonatele unei locatii (in ordinea abscisa ordonata).
Pe urmatoarea linie se afla un numar natural N,
reprezentând numarul de camine studentesti.
Pe fiecare dintre urmatoarele N
linii se afla informatii despre câte un camin sub forma a trei numere
întregi separate prin câte un spatiu X
Y S cu semnificatia "în punctul de coordonate X,
Y exista un camin studentesc
în care locuiesc S studenti".
Date de iesire
Fisierul de iesire pizza1.out
va contine o singura linie pe care va fi scris numarul maxim de clienti siguri
pe care Vasile se poate baza.
Restrictii
1 <= K <= 10
1 <= R <= 500
K <= M <= 20
Toate coordonatele sunt numere întrregi, -1000
<= X,Y <= 1000
1 <= N <= 100
1 <= S <=100
Spunem ca un camin este în raza de actiune a unei pizzerii daca
distanta de la camin la pizzerie este mai mica sau egala cu R.
Nu exista doua locatii cu aceleasi coordonate.