Артур купил большой и красивый стол в свою новую квартиру. Придя домой, Артур обнаружил, что его покупка стоит неустойчиво и сильно шатается.
У стола, купленного Артуром, всего n ножек, длина i-й ножки равна li.
Артур решил сделать стол устойчивым и открутить некоторые ножки. Для каждой из них Артур определил число di — сколько единиц энергии он потратит, чтобы открутить i-ю ножку.
Стол с k ножками считается устойчивым, если ножек максимальной длины строго больше половины. Например, чтобы стол с 5-ю ножками был устойчивым, необходимо, чтобы ножек максимальной длины (среди этих пяти) было хотя бы три. Также, стол с одной ножкой всегда устойчивый, а стол с двумя ножками устойчив тогда и только тогда, когда они имеют равные длины.
Перед вами стоит задача помочь Артуру и посчитать минимальное число единиц энергии, которое Артур может затратить, чтобы сделать стол устойчивым.
Выходные данные
Выведите одно целое число — минимальное число единиц энергии, которое нужно затратить Артуру, чтобы сделать стол устойчивым.