Tranzit
Ujlandiya əlverişli coğrafi mövqeyə malikdir, çünki onun ərazisi vacib ticarət yollarının kəsişməsində yerləşir. Bu yollardan biri də qonşu qardaş dövlətin öz unikal qızdırıcılarını digər ölkələrə çatdırdığı ticarət yoludur.
Ujlandiya və qardaş dövlətin sərhədində, bu yolun başladığı yerdə, hər gün çox sayda qızdırıcı ilə dolu qatarın keçdiyi xüsusi keçid məntəqəsi yerləşir. Yaxınlarda iki qardaş ölkənin hökumətləri arasında Ujlandiya ərazisindən qızdırıcıların tranziti üçün yeni qaydalar razılaşdırılıb. Yeni müqaviləyə əsasən, müəyyən bir m sayı seçilməlidir - bir qatarın içindəki maksimum qızdırıcı sayı. Beləliklə, A[i]
qızdırıcı daşıyan hər qatar üçün dəqiq A[i]
-m ədəd xarici məhsul boşaldılacaq (təbii ki, əgər A[i]
> m olarsa, əks halda qatar heç bir yerdə dayanmadan hərəkət edəcək və heç nə boşaldılmayacaq). Bu, əslində, Ujlandiya ərazisindən keçən qatarın keçid haqqı olacaq, bu dəmir yollarının saxlanma xərclərinə bərabərdir. N gün ərzində Ujlandiyada boşaldılan qızdırıcıların ümumi sayı K-dən az olmamalıdır, əks halda ölkə zərərə uğrayacaq.
N gün ərzində qatarda olan qızdırıcıların sayı məlumdur (bu məlumat müqavilə şərtlərinə əsasən verilir). Ujlandiyanın iqtisadi zərər görməməsi üçün maksimum m sayını tapın.
Giriş məlumatlarının formatı:
Birinci sətirdə iki ədəd N, K (1 ≤ N ≤ 10^6
, 1 ≤ K ≤ 2 *10^9
) yazılıb. Növbəti sətirdə N ədəd - hər gün qatarda olan qızdırıcıların sayı verilib, bu ədəd 10^9
-u keçmir.
Çıxış məlumatlarının formatı:
Tək sətirdə məsələnin cavabını verin, cavabın həmişə mövcud olduğu təmin edilir.
Misal üçün izah:
Ujlandiya ərazisindən cəmi 4 qatar 11, 6, 1 və 8 qızdırıcı ilə keçəcək. Ölkənin zərər görməməsi üçün ən azı 7 qızdırıcı boşaldılmalıdır. Aydındır ki, bu şərti təmin edən maksimum mümkün m 6 olacaq, belə ki, qatarlar müvafiq olaraq 5, 0, 0, 2 qızdırıcı boşaldacaq, bu da cəmi 7 edir və şərti təmin edir.