Pracsiu Dan (dnprx) 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.
Atenție! În fiecare zi arbustul întâi crește și apoi se fac tăierile.
Cerința
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.
Date de intrare
De la tastatură se citesc de 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.
Date de ieșire
Afișați la ecran un număr nenegativ reprezentând înălţimea minimă a celui mai înalt arbust după cele M zile.
Restricții și precizări
1 ≤ k ≤ 1.0001 ≤ x ≤ 10.0000 ≤ height[i] ≤ 10.0000 ≤ dailyGrowth[i] ≤ 10.000- Pentru 8 puncte,
N ≤ 100,M = 1,k = 1,x = 1,height[i] ≥ 1,dailyGrowth[i] = 0 - Pentru 22 puncte,
1 ≤ N, M ≤ 500 - Pentru 43 puncte,
1 ≤ N, M 5.000 - Pentru 27 puncte,
1 ≤ N, M ≤ 10.000
Exemplu:
Intrare
4 3 4 3 2 5 3 2 0 4 2 8
Ieșire
8
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:
