İnək rəqs şousu
После bir neçə aylıq məşqlərdən sonra inəklər illik rəqs tamaşasını - "Cowpelia" baletini təqdim etməyə hazırdırlar.
Səhnənin ölçüsü hələ dəqiqləşdirilməyib. k ölçüsündə bir səhnə eyni anda k inəyi rəqs etməyə dözə bilər. Sürüdəki n inək rəqs zamanı səhnədə görünməli olduqları ardıcıllıqla 1 .. n nömrələnib. Hər bir inək i müəyyən bir müddət rəqs etməyi planlaşdırır d(i). Əvvəlcə 1 .. k inəkləri səhnəyə çıxır və rəqs etməyə başlayır. Bu inəklərdən birincisi rəqsini bitirdikdə, səhnəni tərk edir və k + 1 inəyi dərhal rəqs etməyə başlayır və s. Beləliklə, həmişə k inək rəqs edir, şounun son hissəsi istisna olmaqla, inəklər gedir, amma əlavə olunmur. Şou son inək rəqsini t vaxtında bitirdikdə başa çatır.
Aydındır ki, k dəyəri nə qədər böyükdürsə, t vaxtı bir o qədər azdır. Şou çox uzun davam edə bilməz, buna görə də sizə maksimum mümkün t dəyərini göstərən T[max] yuxarı həddi verilir. Sizin vəzifəniz uyğun olan ən kiçik k dəyərini müəyyən etməkdir.
Giriş Məlumatları
Birinci sətir n (1 ≤ n ≤ 10000) və T[max] ədədini ehtiva edir, burada T[max] 10^6-dan çox olmayan tam ədəddir.
Növbəti n sətir inəklər 1 .. n üçün rəqs müddətlərini d(1) .. d(n) müəyyən edir. Hər bir d(i) 1 .. 10^5 intervalında tam ədəddir.
Zəmanət verilir ki, əgər k = n olarsa, şou vaxtında başa çatacaq.
Çıxış Məlumatları
T[max] vaxt vahidindən çox olmayan bir müddətdə rəqs şousunun bitməsi üçün mümkün olan ən kiçik k dəyərini çıxarın.