B. Удаления с меняющейся четностью
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Поликарпа есть массив $$$a$$$, состоящий из $$$n$$$ целых чисел.

Он хочет поиграть в игру с этим массивом. Игра состоит из нескольких шагов. Во время первого хода он выбирает любой элемент и удаляет его (после первого хода массив содержит $$$n-1$$$ элемент). Для каждого из следующих ходов он выбирает любой элемент с одним ограничением: его четность должна отличаться от четности элемента, удаленного во время прошлого хода. Другими словами, он меняет четности (четный-нечетный-четный-нечетный-... или нечетный-четный-нечетный-четный-...) удаляемых элементов. Поликарп останавливается, если не может совершить ход.

Формально:

  • Если сейчас первый ход, он выбирает элемент и удаляет его;
  • Если это второй или любой следующий ход:
    • если последний удаленный элемент был нечетным, Поликарп выбирает любой четный элемент и удаляет его;
    • если последний удаленный элемент был четным, Поликарп выбирает любой нечетный элемент и удаляет его.
  • Если после какого-то хода Поликарп не может сделать ход, игра заканчивается.

Цель Поликарпа — минимизировать сумму неудаленных элементов массива после конца игры. Если Поликарп может удалить массив целиком, тогда сумма неудаленных элементов равна нулю.

Помогите Поликарпу найти это значение.

Входные данные

Первая строка входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2000$$$) — количество элементов в $$$a$$$.

Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^6$$$), где $$$a_i$$$ — $$$i$$$-й элемент $$$a$$$.

Выходные данные

Выведите одно целое число — минимально возможную сумму неудаленных элементов массива после конца игры.

Примеры
Входные данные
5
1 5 7 8 2
Выходные данные
0
Входные данные
6
5 1 2 4 6 3
Выходные данные
0
Входные данные
2
1000000 1000000
Выходные данные
1000000