== include(page="template/taskheader" task_id="tower") ==
Poveste şi cerinţă...
Vă jucaţi un joc de apărare a turnurilor pe o grilă. Unele celule de pe grilă conţin roci prin care nu se trece, unele conţin inamici, iar altele sunt libere. Trebuie plasat un singur turn laser pe o celulă liberă. Odată plasat, turnul trage cu raze laser în direcţiile nord, sud, est şi vest. Raza îşi continuă drumul până iese din grilă sau loveşte o rocă, distrugând toţi inamicii de pe acea cale. Fiecare inamic distrus valorează un anumit punctaj. Scorul vostru final este suma valorilor fiecărui inamic distrus. Aflaţi scorul maxim posibil.
h2. Date de intrare
Fişierul de intrare $tower.in$ ...
Fişierul de intrare $tower.in$ conţine două numere întregi pe prima linia, $M$ şi $N$, reprezentând numărul de linii, respectiv de coloane al grilei. A doua linie conţine două numere întregi $R$ şi $E$, reprezentând numărul de roci şi numărul de inamici. Următoarele $R$ linii conţin o pereche de numere întregi $l$ şi $c$, coordonatele liniei şi coloanei unei celule în care se află o rocă. Pe fiecare din cele $E$ linii care succedă se găseşte un triplet $l$ $c$ $s$, reprezentând coordonatele celulei unui inamic şi numărul de puncte câştigate în urma distrugerii sale.
h2. Date de ieşire
În fişierul de ieşire $tower.out$ ...
În fişierul de ieşire $tower.out$ se va afişa un singur număr, valoarea maximă scorului final, posibilă pentru configuraţia dată.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ M, N ≤ 1.000.000.000$
* $1 ≤ R, E ≤ 100.000$
* $1 ≤ l ≤ M$ şi $1 ≤ c ≤ N$ pentru toate coordonatele
* $1 ≤ s ≤ 10.000$ pentru toate punctajele inamicilor
* O celulă conţine cel mult un inamic sau o rocă.
* Pentru $10%$ dintre teste $M, N, R, E ≤ 1.000$
* Pentru alte $20%$ dintre teste $R, E ≤ 1.000$
* Pentru alte $30%$ dintre teste $R, E ≤ 30.000$
h2. Exemplu
table(example). |_. tower.in |_. tower.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 10 10
3 6
2 3
1 5
6 3
5 2 40
5 5 10
5 6 30
1 3 20
2 5 50
3 3 10
|90
|
h3. Explicaţie
...
Amplasând turnul la coordonata $(5, 3)$ se obţin $90$ de puncte $(40 + 10 + 10 + 30)$.
Dacă am fi plasat turnul la coordonata $(5, 5)$ am fi obţinut mai multe puncte, însă turnul trebuie plasat pe o celulă liberă.
== include(page="template/taskfooter" task_id="tower") ==
