İnəklərin rəqs şousu#10547
Bir neçə aylıq məşqdən sonra inəklər artıq öz illik rəqs çıxışlarını təqdim etməyə demək olar ki, hazırdırlar. Bu il onlar məşhur inək baletini — «Cowpelia»nı ifa edirlər.
Çıxış üçün müəyyən edilməli olan yeganə şey — səhnənin ölçüsüdür. ölçülü səhnə eyni vaxtda rəqs edən inəyi tuta bilər. Sürüdəki inəklər səhnəyə çıxmalı olduqları ardıcıllıqla 1, \ldots, n nömrələri ilə nömrələnmişdir. Hər bir inəyi uzunluğunda müəyyən bir zaman intervalı ərzində rəqs etməyi planlaşdırır.
Əvvəlcə 1, \ldots, k inəkləri səhnəyə çıxır və rəqs etməyə başlayırlar. Bu inəklərdən birinci hissəsini bitirən kimi səhnəni tərk edir, və k + 1 inəyi dərhal rəqs etməyə başlayır. Bu proses davam edir, buna görə də səhnədə həmişə eyni vaxtda inək rəqs edir (çıxışın sonuna qədər, o zaman ki, qalan inəklərin sayı -dan az olur).
Çıxış son inəyin öz rəqs hissəsini bitirdiyi anında başa çatır.
Aydındır ki, dəyəri nə qədər böyük olarsa, dəyəri bir o qədər kiçik olar. Çıxış çox uzun çəkməməli olduğundan, sizə onun müddətinə T_{\max} məhdudiyyəti verilir. Bu məhdudiyyət daxilində, mümkün olan minimum dəyərini müəyyən edin.
Birinci sətirdə n~(1 \le n \le 10000) və T_{\max} verilir, burada T_{\max} — 10^6-dan çox olmayan tam ədəddir.
Sonrakı sətirdə uyğun olaraq 1, \ldots, n inəklərinin rəqs hissələrinin d(1), \ldots, d(n) uzunluqları verilir. Hər bir dəyəri 1, \ldots, 10^5 diapazonunda tam ədəddir.
Zəmanət verilir ki, k = n olduqda çıxış müəyyən edilmiş zaman məhdudiyyəti daxilində başa çatır.
Rəqs çıxışının T_{\max} vahid zamandan artıq davam etmədiyi mümkün olan minimum dəyərini çap edin.
Nümunə 1