Задача №114953. Аборигены
Капитан Кук с командой попали в плен к аборигенам. Чтобы избежать участи быть съеденными, путешественники предложили аборигенам поделиться с ними сокровищами. Оказалось, что у капитана и его команды есть \(n\) сокровищ.
Главный шаман согласен отпустить капитана с командой, если они отдадут им не меньше половины своих сокровищ. Все сокровища выглядят красиво, поэтому шаман согласен на любые сокровища, главное, чтобы их было не меньше половины.
Однако для Кука сокровища представляют определенную ценность. Он считает ценность \(i\)-го сокровища равной \(a_i\). Помогите капитану определить, какие сокровища отдать аборигенам, чтобы его с товарищами отпустили, а суммарная ценность оставшихся в распоряжении команды сокровищ была максимальной.
На первой строке ввода находится число \(n\) (\(2 \le n \le 1000\)).
На второй строке находятся \(n\) натуральных чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 1000\)).
Выведите одно целое число — максимальную суммарную ценность сокровищ, которые могут остаться у капитана Кука и его команды, если они отдадут не менее половины сокровищ аборигенам.
В примере Кук может отдать сокровища со стоимостью \(1\), \(2\) и \(3\) шаману, оставив себе сокровища со стоимостью \(3\), \(4\) и \(5\). Их суммарная стоимость равна \(3+4+5=12\).
6 2 4 1 3 3 5
12