Müasir incəsənət
Əgər siz "Arsenal" müasir incəsənət sərgisində olmusunuzsa, oradakı eksponatların nə qədər böyük mədəni dəyərə malik olduğunu bilirsiniz. Odessa paytaxtdan geri qalmamaq qərarına gəldi və şəhərimizin sakinlərinin gücü ilə müasir incəsənətin şah əsəri - qəhvə stəkanlarından ibarət qüllələr ardıcıllığı tikildi!
Eksponat, mərkəzi küçənin bir ucundan digərinə qədər ardıcıl yerləşdirilmiş müxtəlif hündürlüklərdə n qüllədən ibarətdir. Lakin, incəsənəti qiymətləndirməyən və gözəllik hissi olmayan vandal (və eyni zamanda idman proqramçıları), gecə bir neçə (və ya bir neçə milyon, nə qədər kiçik düşünək) fincan qəhvə içmək qərarına gələrək m stəkan istifadə etdilər, bununla da bəzi qüllələrin hündürlüyünü dəyişdirdilər. Bu əməldən sonra i-ci qüllənin hündürlüyü A_i oldu. Qüllələri təcili olaraq bərpa etmək lazımdır, bu zaman əldə edilən ekspozisiyanın gözəlliyi mümkün qədər böyük olmalıdır. Bu şah əsərin gözəlliyi, qüllələrin gözəl ardıcıllığının maksimum uzunluğu adlanır. l-dən r-ə qədər (1 ≤ l ≤ r ≤ n) qüllələr ardıcıllığı gözəl adlanır, əgər H_l=H_{l+1}=...=H_r olarsa, burada H_i - stəkanlar əlavə edildikdən sonra i-ci qüllənin hündürlüyüdür.
Bu vəzifə Odessanın ən məsuliyyətli qızlarına həvalə edilmişdi, lakin onlar hansısa məktəbə getdilər, buna görə də bu məsələni ora göndərmək məcburiyyətində qaldıq və siz də həll edəcəksiniz: mövcud olanlara ən çox m stəkan əlavə edərək əldə edilə biləcək maksimum qüllə gözəlliyini çıxarın. Unutmayın ki, yeni qüllələr yaratmaq olmaz, qalan stəkanları götürmək də olmaz.
Giriş verilənləri
Birinci sətirdə iki ədəd n (1 ≤ n ≤ 10^6) və m (0 ≤ m ≤ 10^9) verilir. Növbəti sətirdə boşluqla ayrılmış n ədəd A_{i }(1 ≤ A_{i }≤ 10^9) verilir, i-ci ədəd i-ci qüllənin hündürlüyünə bərabərdir.
Çıxış verilənləri
Tək bir ədəd çıxarın - əldə edilə biləcək eksponatın maksimum gözəlliyi.