У Поликарпа есть массив \(a\), состоящий из \(n\) целых чисел.
Он хочет поиграть в игру с этим массивом. Игра состоит из нескольких шагов. Во время первого хода он выбирает любой элемент и удаляет его (после первого хода массив содержит \(n-1\) элемент). Для каждого из следующих ходов он выбирает любой элемент с одним ограничением: его четность должна отличаться от четности элемента, удаленного во время прошлого хода. Другими словами, он меняет четности (четный-нечетный-четный-нечетный-... или нечетный-четный-нечетный-четный-...) удаляемых элементов. Поликарп останавливается, если не может совершить ход.
Формально:
- Если сейчас первый ход, он выбирает элемент и удаляет его;
- Если это второй или любой следующий ход:
- если последний удаленный элемент был нечетным, Поликарп выбирает любой четный элемент и удаляет его;
- если последний удаленный элемент был четным, Поликарп выбирает любой нечетный элемент и удаляет его.
- Если после какого-то хода Поликарп не может сделать ход, игра заканчивается.
Цель Поликарпа — минимизировать сумму неудаленных элементов массива после конца игры. Если Поликарп может удалить массив целиком, тогда сумма неудаленных элементов равна нулю.
Помогите Поликарпу найти это значение.
Выходные данные
Выведите одно целое число — минимально возможную сумму неудаленных элементов массива после конца игры.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 5 7 8 2
|
0
|
|
2
|
6
5 1 2 4 6 3
|
0
|
|
3
|
2
1000000 1000000
|
1000000
|