E. Feruz Ustaning Munchoqlari

Qadim zamonlarda mashhur bo'lgan Feruz degan zargar ustaning bisotida n dona nodir munchoq saqlanar edi, ularning har biri o'ziga xos vaznga ega bo'lib, bu vaznlar \(a_1, a_2, \dots, a_n\) qiymatlar bilan ifodalanardi.

Ustaning bir g'alati odati bor edi: u ustaxonasini yopishdan burun, qo'lidagi munchoqlarni birma-bir savdogarlarga hadya qilib yuborardi. Biroq bu hadya jarayoni ixtiyoriy tartibda emas, balki qat'iy bir intizom asosida kechardi. Dastlabki hadya etiladigan munchoqni usta o'zi xohlagancha, erkin tanlab olardi. Ammo undan keyingi har bir qadamda hadya qilinadigan munchoqning vazni juftlik xususiyati jihatidan oldingi hadya etilgan munchoqnikidan albatta farqli bo'lishi shart edi: agar avvalgi munchoqning vazni toq son bo'lsa, endigisi so'zsiz juft son bo'lishi lozim edi, va aksincha. Qaysidir bosqichda ushbu talabga javob beradigan munchoq qolmasa, hadya jarayoni beixtiyor to'xtab qolardi, va shu topilgan zahoti qo'lida qolgan munchoqlar abadiy uning xazinasida saqlanib qolaverardi.

Feruz usta o'ta hisobli va tejamkor kishi bo'lgani bois, u o'z bisotida qolib ketadigan munchoqlarning umumiy vazni imkon qadar oz bo'lishini orzu qilardi. Shu maqsadda u dastlabki qadamda qaysi munchoqni tanlashni va har keyingi bosqichda qaysi mos munchoqqa qo'l urishni — aynan shu maqsad, ya'ni qo'lida qolib ketadigan munchoqlar vaznining yig'indisini eng kamiga tushirish — yo'lida hal etardi.

Sizdan talab qilinadigan: berilgan \(n\) ta munchoqning vaznlari asosida, Feruz usta eng unumli tarzda harakat qilganda, jarayon yakunida uning huzurida qolib ketadigan munchoqlar vaznining eng kichik mumkin bo'lgan yig'indisini toping.

Kiruvchi ma'lumotlar

Birinchi qatorda bitta butun son \(n (1 \le n \le 2000)\) — munchoqlar soni keltiriladi.
Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \dots, a_n\) \((0 \le a_i \le 10^6)\) — har bir munchoqning vazni keltiriladi.

Chiquvchi ma'lumotlar

Yagona butun son — jarayon yakunlangach ustaning huzurida qolib ketgan munchoqlar vaznining minimal yig'indisi.

Misollar

1

5
1 5 7 8 2

0

2

6
5 1 2 4 6 3

0

3

2
1000000 1000000

1000000