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

Poveste şi cerinţă...

Pe faleza râului Prahova primarul oraşului Ploieşti a plantat un şir de N arbuşti ornamentali de diverse soiuri, fiecare arbust $i$ având iniţial înălţimea $height[i], 1 ≤ i ≤ N$. În funcţie de solul în care este plantat şi de vreme, arbustul $i$ creşte zilnic cu înălţimea $dailyGrowth[i]$.
 
În fiecare zi grădinarul primăriei ajustează, prin tăiere cu o foarfecă, înălţimea arbuştilor. Totuşi, grădinarul este limitat de detaliile tehnice ale foarfecii. Astfel, acesta poate tăia la o tăietură exact $x$ centimetri din înălţimea unui arbust dacă înălţimea este cel puţin $x$ (de notat faptul că arbustul poate ajunge la înălţimea $0$ după o tăietură). Pentru a nu se obosi, grădinarul poate să efectueze într-o zi cel mult $k$
tăieturi. Grădinarul poate să efectueze mai multe tăieturi asupra unui arbust într-o zi.
 
Primarul organizează după $M$ zile un eveniment artistic şi doreşte să aflaţi care este înălţimea minimă a celui mai înalt arbust după cele $M$ zile.
 
*Atenţie!* În fiecare zi arbustul întâi creşte şi apoi se fac tăierile

h2. Date de intrare

Fişierul de intrare $waterfront.in$ ...

Fişierul de intrare $waterfront.in$ e conţine pe prima linie numerele naturale $N, M, k$ şi $x$. Pe următoarele N linii se află câte două numere naturale $height[i]$ şi $dailyGrowth[i]$, separate prin spaţiu.

h2. Date de ieşire

În fişierul de ieşire $waterfront.out$ ...

În fişierul de ieşire $waterfront.out$ se va afla un număr nenegativ reprezentând înălţimea minimă a celui mai înalt arbust după cele $M$ zile.
 

h2. Restricţii

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

* $1 ≤ k ≤ 1 000$
* $1 ≤ x ≤ 10 000$
* $1 ≤ height[i] ≤ 10 000$
* $1 ≤ dailyGrowth[i] ≤ 10 000$
* În plus:
 
table(restrictii). |_. # |_. Punctaj |_. Restricţii |
| $1$ | $8$ | $N ≤ 100, M = 1, k = 1, x = 1, height[i] ≥ 1, dailyGrowth[i] = 0$ |
| $2$ | $22$ | $1 ≤ N, M ≤ 500$ |
| $3$ | $43$ | $1 ≤ N, M ≤ 5 000$ |
| $4$ | $27$ | $1 ≤ N, M ≤ 10 000$ |
 

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

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

| 4 3 4 3
  2 5
  3 2
  0 4
  2 8
| 8

|
h3. Explicaţie

...

Grădinarul taie arbuştii în $3$ zile, în fiecare zi făcând câte $4$ tăieturi. La fiecare tăietură poate elimina câte $3$ cm din înălţimea arbustului. Următorul tabel ilustrează modul optim de efectuare a tăierilor:
 
!problema/waterfront?WaterFront.jpeg!

== include(page="template/taskfooter" task_id="waterfront") ==