Landşaftın yaxşılaşdırılması
Luis LeRua Universitetinin kral sarayından görünən mənzərəni yaxşılaşdırmaq əmri verilib. Onun Əlahəzrəti yüksək bir dağa baxmağı üstün tutur.
Əsas Landşaft Meneceri, Luis üçün dağın hündürlüyünü artırmağı planlaşdırır. Mənzərə, vahid kvadrat şəbəkəsində düz bir şəkil kimi təqdim olunur. Bəzi kvadratlar artıq daşla doldurulub, digərləri isə boşdur. Bu, tikintini xeyli asanlaşdırır. Vahid kvadratlar kifayət qədər kiçikdir və mənzərə kral sarayından hamar görünür.
Əsas Landşaft Menecerinin landşaft planı var - bütün en boyunca daşla doldurulmuş sütunların hündürlükləri. O, mövcud mənzərənin üstünə ən çox n kvadrat daş plitələr əlavə etməyi planlaşdırır ki, mənzərənin hündürlüyü maksimum olsun. Təəssüf ki, daş yığınları olduqca qeyri-sabitdir. Kvadrat daş bloku yalnız başqa bir daşın üstünə yerləşdirilə bilər, həmçinin onun altındakı sol və sağ kvadratlar da doldurulmalıdır.
Əsas Landşaft Menecerinə, o, ən böyük dağ hündürlüyünü müəyyən etməyə kömək etməlisiniz.
Giriş Məlumatları
Birinci sətir iki ədəd ehtiva edir: w - mövcud mənzərənin eni və n - əlavə edilə biləcək maksimum kvadrat daşların sayı (1 ≤ w ≤ 10^5, 0 ≤ n ≤ 10^18).
Növbəti w sətirin hər biri bir ədəd h[i] (1 ≤ h[i] ≤ 10^9) ehtiva edir - landşaft sütununun başlanğıc hündürlüyü.
Çıxış Məlumatları
Bütün quruluşun sabitliyi şərti ilə ən çox n vahid kvadrat daş əlavə edildikdən sonra mənzərənin mümkün olan ən böyük hündürlüyünü çıxış edin.