Qurutma#5363
Qışda paltar yumaq — çətin bir işdir, amma onu qurudmaq daha da çətindir. Ancaq Ceyn — ağıllı bir qızdır və gündəlik işlərdən çəkinmir. Quruma prosesini sürətləndirmək üçün o, radiator istifadə etmək qərarına gəldi. Lakin radiator kiçikdir və hər an yalnız bir əşyanı qurutmağa qadirdir.
Ceyn paltarını mümkün qədər tez qurumaq istəyir. O, sizdən paltarların hamısını qurutmaq üçün lazım olan minimum müddəti müəyyənləşdirən bir proqram yazmağınızı xahiş edir.
Ceyn yeni yuyulmuş əşya aldı. Yuma zamanı hər bir əşya a_i vahid su udur. Hər dəqiqə ərzində, əgər əşya hələ qurumamışdırsa, onun tərkibində olan suyun miqdarı bir vahid azalır. Su miqdarı sıfıra bərabər olan kimi əşya quru sayılır və yığmaq üçün hazırdır.
Bundan əlavə, hər dəqiqə Ceyn bir əşyanı seçib radiatora qoya bilər. Radiator kifayət qədər istidir, buna görə də onun üstündəki əşya dəqiqədə vahid su itirir (lakin olan sudan daha çox deyil: əgər əşyada vahiddən az su varsa, o, həmin dəqiqə tamamilə quruyur).
Sizin vəzifəniz — radiatorun optimal istifadəsi ilə bütün paltarların qurutulması üçün lazım olan minimal vaxtı müəyyən etməkdir. Qurutma işinin tamamlanmış olduğu haqda deyilir ki, o zaman bütün paltarlar quru olsun.
Birinci sətir bir tam ədəd n~(1 \le n \le 10^5) — əşyaların sayını ehtiva edir.
İkinci sətir tam ədəd a_i~(1 \le a_i \le 10^9) ehtiva edir, burada a_i — yuyulmadan sonra -ci əşyadakı suyun miqdarıdır.
Üçüncü sətir bir tam ədəd k~(1 \le k \le 10^9) ehtiva edir — radiatorun üstündəki əşyadan suyun buxarlanma sürəti (dəqiqədə su vahidləri ilə).
Bir ədəd çıxarın — bütün əşyaların tam qurutulması üçün tələb olunan minimum dəqiqə sayı.
Nümunə 1
Nümunə 2