copaci2

Copaci 2

== include(page="template/taskheader" task_id="copaci2") ==

Poveste si cerinta...

Zaharel are $N$ copaci in gradina din spatele casei sale, asezati in linie, numerotati convenabil de la stanga la dreapta cu numere de la $1$ la $N$. Dorind ca gradina lui sa arate cat mai frumos si uniform lui si-a propus sa minimize diferenta maxima intre inaltimile copacilor adiacenti. Copacii nu pot fi mutati din loc, dar inaltimile lor pot fi micsorate sau marite (folosind tehnici moderne de gradinarit). Fiecare copac are o inaltime $H{~i~}$ si un cost $C{~i~}$ de a ii mari sau micsora inaltimea cu o unitate.
Stiind ca are la dispozitie un buget de valoare $K$ determinati valoarea minima pentru diferenta maxima intre inaltimile copacilor adiacenti.

h2. Date de intrare

Fisierul de intrare $copaci2.in$ ...

Pe prima linie a fisierului de intrare $copaci2.in$ sunt scrise cele doua numere naturale $N, K$, separate prin spatii. Pe urmatoarele $N$ linii se vor scrie cate doua numere naturale $H{~i~}, C{~i~}$, separate prin spatii.

h2. Date de iesire

In fisierul de iesire $copaci2.out$ ...

Prima linie a fisierului $copaci2.out$ va contine un singur numar natural reprezentand valoarea minima pentru diferenta maxima intre inaltimile copacilor adiacenti.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 1.000$
* $1 ≤ K ≤ 10^9^$
* $1 ≤ H{~i~}, C{~i~} ≤ 1.000$
* Un copac poate fi micsorat pana la inaltimea $0$

h2. Exemplu
table(example). |_. copaci2.in |_. copaci2.out |

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

| 6 9
8 3
9 2
4 3
7 6
4 2
3 4
|2|

h3. Explicatie