Masala #0849

Xotira 16 MB Vaqt 1000 ms

Tuxum biznesi

Shahriyor yaqinda tuxum biznesi haqida o'qib qoldi. Uyida bittagina tovug'i bor edi. Tovuq har kuni ertalab bitta tuxum qo'yadi va Shahriyor tuxumlarni yeb qo'yardi. U endi ertadan boshlab tovug'ining tuxumlarini bozorga sotishga qaror qildi. Bozordagi narxlar esa har kuni o'zgarib turadi. Shahriyorda tuxumning keyingi \(n\) kunlik narxlar jadvali bor va u shu kunlar davomida maksimal daromad topishni xohlaydi.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(n(1 \le n \le 10^5)\) natural son kiritiladi.
Ikkinchi qatorda har bir \(i\)-kun uchun bitta tuxumning \(C_i\) qiymatiga to'g'ri keladigan 1000 dan oshmaydigan \(n\) ta natural sonlar bo'sh joy bilan ajratilgan holda beriladi.

Chiquvchi ma'lumotlar:

Bitta butun son Shahriyor kelasi \(n\) kun ichida ishlay oladigan maksimal pul miqdorini chop etishingiz kerak.

Misollar

#	input.txt	output.txt
1	5 73 31 96 24 46	380
2	10 1 2 3 4 5 6 7 8 9 10	100

Izoh:

1-testda 1 va 2-kuni tuxumlarni sotmaydi va 3-kuni 3 ta tuxumni 96 so'mdan 288 so'mga sotadi, 4 va 5-kunlik tuxumlarni 46 so'mdan 92 so'mga sotadi va jami 380 so'm daromad qiladi.