Copaci 2

copaci2

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

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.

Poveste si cerinta...

h2. Date de intrare

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.

Fisierul de intrare $copaci2.in$ ...

h2. Date de iesire

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

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

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 |

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

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

h3. Explicatie