copaci

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 el 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 pentru a ii mari sau micsora inaltimea cu o unitate. 

Cerinta

Stiind ca are la dispozitie un buget de valoare K determinati valoarea minima pentru diferenta maxima intre inaltimile copacilor adiacenti.

Date de intrare

Pe prima linie a fisierului de intrare copaci.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.

Date de iesire

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

Restrictii

• 1 ≤ N ≤ 1.000
• 1 ≤ K ≤ 10⁹
• 1 ≤ H_i, C_i ≤ 1.000
• Un copac poate fi micsorat pana la inaltimea 0

Exemplu

copaci.in	copaci.out	Explicatie
6 9 8 3 9 2 4 3 7 6 4 2 3 4	2	Se micsoreaza inaltimea copacului 2 cu 2 unitati si se mareste inaltimea copacilor 3 si 5 cu o unitate. Noile inaltimi vor fi 8, 7, 5, 7, 5, 3 si diferenta maxima intre inaltimile copacilor adiacenti este 2. Costul total este 2*2 + 1*3 + 1*2 = 9.

Timp maxim de executie/test: 0.3 secunde
Memorie totala disponibila 2MB, din care 1 MB pentru stiva

Mircea Paşoi
Universitatea Bucuresti, Facultatea de Matematica si Informatica
mircea.pasoi@gmail.com