Polycarp has an array a consisting of n integers.

He wants to play a game with this array. The game consists of several moves. On the first move he chooses any element and deletes it (after the first move the array contains n-1 elements). For each of the next moves he chooses any element with the only restriction: its parity should differ from the parity of the element deleted on the previous move. In other words, he alternates parities (even-odd-even-odd-... or odd-even-odd-even-...) of the removed elements. Polycarp stops if he can't make a move.

Formally: 

  * If it is the first move, he chooses any element and deletes it; 
  * If it is the second or any next move: 
    * if the last deleted element was odd, Polycarp chooses any even element and deletes it; 
    * if the last deleted element was even, Polycarp chooses any odd element and deletes it. 
  * If after some move Polycarp cannot make a move, the game ends. 



Polycarp's goal is to minimize the sum of non-deleted elements of the array after end of the game. If Polycarp can delete the whole array, then the sum of non-deleted elements is zero.

Help Polycarp find this value.

Input

The first line of the input contains one integer n (1 ≤ n ≤ 2000) — the number of elements of a.

The second line of the input contains n integers a_1, a_2, ..., a_n (0 ≤ a_i ≤ 10^6), where a_i is the i-th element of a.

Output

Print one integer — the minimum possible sum of non-deleted elements of the array after end of the game.

Examples

Input


5
1 5 7 8 2


Output


0


Input


6
5 1 2 4 6 3


Output


0


Input


2
1000000 1000000


Output


1000000
#include <bits/stdc++.h>
using namespace std;
long long int com(long long int n, long long int a) {
  long long int result = 1;
  if (n - a < a) a = n - a;
  long long int cnt = 1;
  for (long long int i = n - a + 1; i < n + 1; i++) {
    result *= i;
    result /= cnt;
    cnt++;
  }
  return result;
}
void swap(int *xp, int *yp) {
  int temp = *xp;
  *xp = *yp;
  *yp = temp;
}
void bubbleSort(int arr[], int n) {
  int i, j;
  for (i = 0; i < n - 1; i++)
    for (j = 0; j < n - i - 1; j++)
      if (arr[j] > arr[j + 1]) swap(&arr[j], &arr[j + 1]);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  long long int test = 1;
  while (test > 0) {
    long long int n;
    cin >> n;
    vector<int> o, e;
    long long int a[n], j = 0, k = 0;
    for (long long int i = 0; i < n; i++) {
      cin >> a[i];
      if (a[i] % 2 == 0) {
        e.push_back(a[i]);
        j++;
      } else {
        o.push_back(a[i]);
        k++;
      }
    }
    sort(o.begin(), o.end(), greater<int>());
    sort(e.begin(), e.end(), greater<int>());
    long long int mini = min(o.size(), e.size());
    long long int sum1 = 0, sum2 = 0;
    if (abs(k - j) <= 1) {
      cout << "0";
    } else {
      if (j > k) {
        for (long long int i = mini + 1; i < e.size(); i++) {
          sum1 += e[i];
        }
        cout << sum1;
      } else {
        for (long long int i = mini + 1; i < o.size(); i++) {
          sum2 += o[i];
        }
        cout << sum2;
      }
    }
    test--;
  }
}
