Masala #ZRR0KTLFSF

Xotira 256 MB Vaqt 1000 ms

Piter Pen

Kapitan Hookning kemasida \(n\) ta sandiq ketma-ket qo'yilgan. Ma'lumki yonma-yon sandiqlar bir vaqtda ochilsa xavfsizlik tizimi ishga tushadi. Har bir sandiq ichida qanchadir miqdorda oltin bor. Piter Pen kemaga o'g'irlikka tushdi hamda u yerdan imkon qadar tezroq chiqib ketishi zarur. U 1 marta sandiqlarning oldidan uchib o'tish orqali maksimum miqdorda oltin yig'ishni xohlaydi. Shuni ham unutmangki, vaqt tig'izligi sabab Piter Pen hech bir sandiqni yopishga ulgurmaydi.

Piter Pen yig'ishi mumkin bo'lgan maksimum oltinni aniqlang.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(n\) - sandiqlar soni kiritiladi.

Keyingi qatorda \(n\) ta butun son har bir sandiq ichidagi oltin miqdorlari - \(A_i (1 \le i \le n)\) kiritiladi.

\(1 \le n \le 10^6\)

\(1 \le A_i \le 10^9\)

Chiquvchi ma'lumotlar:

Maksimum yig'ish mumkin bo'lgan oltinni chop eting.

Misollar

#	input.txt	output.txt
1	10 1 10 2 2 6 1 6 6 6 1	28
2	5 7 9 6 9 3	18

Izoh:

1-test uchun quyidagi sandiqlardan oltinni olish maksimal foyda keltiradi:

1 10 2 2 6 1 6 6 6 1