== include(page="template/taskheader" task_id="light") ==
Poveste si cerinta...
Avi a ajuns primar in orasul sau natal, iar o prima problema cu care se confrunta este iluminatul public. Strada principala poate fi considerata ca fiind o axa cu originea in punctul O. De-a lungul soselei exista <b>N</b> obiective principale, despre care Avi stie ca se afla la distanta <b>a</b> de punctul O si se intind pe o lungime <b>b</b>. Firma EPT (Electricitate Pentru Tonti) i-a facut o oferta : el va primi maxim <b>nr</b> stalpi de iluminare pentru acelasi pret, si cu aceeasi raza de iluminat, oricare o va cere primarul. Fiecare stalp poate ilumina o portine de lungime <b>R</b> numar intreg, dar intr-un mod ciudat : acesta poate ilumina <b>R1</b> unitati de drum in stanga sa si <b>R2</b> unitati in dreapta sa, cat timp cat <b>R1</b>+<b>R2</b> = <b>R</b>. <b>R1</b> si <b>R2</b> pot fi reglate odata cu amplasarea stalpului, insa <b>R</b> este fix din fabrica. Stiind ca o raza mai mare de iluminat determina un cost mai mare in timp, Avi va roaga sa determinati raza minima pentru care el poate asigura iluminatul obiectivelor principale.
<b>Cerinta</b>
Cunoscand pozitiile de inceput si distanta pe care se intind a fiecarui obiectiv, determinati raza <b>R</b> minima ce o pot avea stalpii pentru a putea ilumina complet fiecare obiectiv, precum si numarul minim de stalpi necesari.
h2. Date de intrare
Fisierul de intrare $light.in$ ...
Fisierul de intrare $light.in$ va contine pe prima linie numarul <b>N</b> de obiective si <b>nr</b> - numarul maxim de stalpi, iar pe urmatoarele <b>N</b> linii cate 2 valori, <b>a[i]</b> - distanta pana in punctul O al obiectivului i, si <b>b[i]</b> - lungimea sa.
h2. Date de iesire
In fisierul de iesire $light.out$ ...
In fisierul de iesire $light.out$ se vor afisa pe o singura linie 2 valori, <b>Rmin</b> si <b>nrmin</b>, reprezetand portiunea iluminata de fiecare stalp, precum si numarul minim de stalpi necesari.
h2. Restrictii
* $... ≤ ... ≤ ...$
* 1 ≤ N ≤ 100.000
* 0 ≤ a[i] ≤ 1.000.000.000
* 1 ≤ b[i] ≤ 1.000.000.000
* 1 ≤ nr ≤ 1.000.000
h2. Exemplu
table(example). |_. light.in |_. light.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4 4
1 4
6 4
16 2
15 2
| 3 4
|
| 4 3
1 4
6 4
16 2
15 2
| 4 3
|
h3. Explicatie
...
In primul caz, stalpul 1 va ilumina portiunea (1, 4), stalpul 2 portiunea (5, 8), stalpul 3 portiunea (9, 12), iar stalpul 4 portiunea (15, 18). In al doilea, stalpul va ilumina portiunea (1, 5), stalpul 2 portiunea (6, 10), iar stalpul 3 portiunea (15, 19);
== include(page="template/taskfooter" task_id="light") ==
