Diferențe pentru problema/combat între reviziile #30 si #8

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 tururi, astfel:

Bătălia se desfășoară pe turnuri, astfel:

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

* La fiecare turn, fiecare navă inamică trage pe rând împotriva navei voastre.
* Dacă nava noastră a rezistat atacurilor din acest turn (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 turnuri.

Bătălia încetează în două cazuri:

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

Misiunea voastră este ca în fiecare turn, să alegeți eficient nava 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$ 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ț.

Fișierul de intrare $combat.in$ ...

h2. Date de ieșire

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

În fișierul de ieșire $combat.out$ ...

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 |

| 2 20 10
5 10
8 4
| 2

| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.

|
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") ==