Nava voastră este atacată de $N$ nave inamice. Fiecare navă $i$ are un număr $h[i]$ de puncte de viață și o armă laser care provoacă o daună egală cu $d[i]$ puncte de viață.
Bătălia se desfășoară pe turnuri, astfel:
Bătălia se desfășoară pe tururi, astfel:
* La fiecare turn, fiecare navă inamică trage pe rând împotriva navei voastre.
* Dacă nava noastră a rezistat atacului din această tură (dacă a rămas cu un număr de puncte de viață mai mare strict decât [$0$]), aceasta va alege o navă inamică și va trage împotriva ei.
* Dacă nava aleasă va fi distrusă în urma atacului, nu va mai participa în următoarea tură.
* La fiecare tur, fiecare navă inamică trage pe rând împotriva navei voastre.
* Dacă nava noastră a rezistat atacurilor din acest tur (dacă a rămas cu un număr de puncte de viață mai mare strict decât [$0$]), aceasta va alege o navă inamică și va trage împotriva ei.
* Dacă nava aleasă este distrusă în urma atacului (dacă a rămas cu un număr de puncte de viață egal cu [$0$]), nu va mai lua parte în următoarele tururi.
Bătălia încetează în două cazuri:
* Fie nava voastră este distrusă.
* Fie toate navele adverse sunt distruse.
h2. Cerință
Misiunea voastră este ca în fiecare tur să alegeți eficient nava inamică pe care să o atacați, astfel încât la finalul bătăliei nava voastră să supraviețuiască. În cazul în care acest lucru este posibil, trebuie să afișați numărul maxim de puncte de viață cu care nava voastră poate încheia bătălia. În cazul în care acest lucru este imposibil și nava este distrusă în urma bătăliei, veți afișa $-1$.
h2. Date de intrare
Fișierul de intrare $combat.in$ ...
Fișierul de intrare $combat.in$ conține pe prima linie $3$ numere naturale despărțite între ele prin câte un spațiu, $N H D$, având semnificația din enunț. Pe fiecare linie $i$ din următoarele $N$ linii, se vor găsi $2$ numere naturale: $h[i] și d[i]$, având semnificația din enunț.
h2. Date de ieșire
În fișierul de ieșire $combat.out$ ...
În fișierul de ieșire $combat.out$ se va găsi un singur număr natural, reprezentând numărul maxim de puncte de viață cu care nava voastră poate încheia bătălia. În cazul în care acest lucru nu este posibil, se va găsi valoarea $-1$.
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 5.000$
* $1 ≤ H ≤ 1.000.000.000$
* $1 ≤ D ≤ 100$
* $1 ≤ h[i], d[i] ≤ 100, pentru orice 1 ≤ i ≤ N$
h2. Exemplu
table(example).
|_. combat.in |_. combat.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2 20 10
5 10
8 4
| 2
|
h3. Explicație
...
Sunt $2$ nave inamice, ambele pot fi distruse cu un singur atac al navei voastre:
* În primul tur vom primi $14$ puncte de daună și vom rămâne astfel cu $20 - 10 - 4 = 6$ puncte de viață. Vom distruge prima navă, pentru că este mai puternică (provoacă o daună mai mare).
* În cel de-al doilea tur vom primi $4$ puncte de daună de la cea de-a doua navă inamică și vom rămâne cu $6 - 4 = 2$ puncte de viață. Vom distruge nava și astfel încheiem bătălia.
Dacă am fi ales să distrugem mai întâi cea de-a doua navă, am fi primit în primul tur $14$ puncte de daună, iar în cel de-al doilea tur încă [$10$], pierzând astfel bătălia.
== include(page="template/taskfooter" task_id="combat") ==
