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 binpow(long long a, long long b) {
  if (b == 0) return 1;
  long long res = binpow(a, b / 2) % 1000000007;
  if (b % 2)
    return (((res * res) % 1000000007) * a) % 1000000007;
  else
    return (res * res) % 1000000007;
}
struct hash_pair {
  template <class T1, class T2>
  size_t operator()(const pair<T1, T2>& p) const {
    auto hash1 = hash<T1>{}(p.first);
    auto hash2 = hash<T2>{}(p.second);
    return hash1 ^ hash2;
  }
};
long long fact(long long n) {
  long long res = 1;
  for (long long i = 2; i <= n; i++) res = (res * i) % 1000000007;
  return (res) % 1000000007;
}
bool isPrime(long long n) {
  if (n == 1) return false;
  if (n == 2) return true;
  for (long long i = 2; i * i <= n; i++)
    if (n % i == 0) return false;
  return true;
}
long long ceil(long long a, long long b) {
  if (a % b == 0) {
    return a / b;
  } else {
    return ((a / b) + 1);
  }
}
long long min(long long a, long long b) {
  if (a > b) {
    return b;
  }
  return a;
}
long long max(long long a, long long b) {
  if (a > b) return a;
  return b;
}
long long dif(long long a, long long b) {
  if (a > b) return a - b;
  return b - a;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) {
  long long k = gcd(a, b);
  return (a * b) / k;
}
void read(long long arr[], long long n) {
  for (long long i = 0; i < n; i++) {
    cin >> arr[i];
  }
}
void addedge(vector<vector<long long>>& v, long long p1, long long p2) {
  v[p1].push_back({p2});
  v[p2].push_back({p1});
}
bool mycmp(pair<long long, float> p1, pair<long long, float> p2) {
  return p1.first < p2.first;
}
void print(long long arr[], long long n) {
  for (long long i = 0; i < n; ++i) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}
bool mycmp2(pair<long long, pair<long long, long long>>& p1,
            pair<long long, pair<long long, long long>>& p2) {
  if (p1.second.first == p2.second.first) {
    return p1.first > p2.first;
  } else {
    return p1.second.first < p2.second.first;
  }
}
vector<long long> prime;
void sieveOferatosthenes(long long MAX) {
  bool pri[MAX + 1];
  memset(pri, true, sizeof(pri));
  pri[1] = false;
  for (long long p = 2; p * p <= MAX; p++) {
    if (pri[p]) {
      for (long long i = p * 2; i <= MAX; i += p) pri[i] = false;
    }
  }
  for (long long i = 1; i <= MAX; i++) {
    if (pri[i]) {
      prime.push_back(i);
    }
  }
}
bool mycmp3(pair<long long, long long>& p1, pair<long long, long long>& p2) {
  if (p1.first == p2.first) {
    return p1.second < p2.second;
  }
  return p1.first < p2.first;
}
void solve() {
  int n;
  cin >> n;
  long long arr[n];
  read(arr, n);
  vector<long long> odd, even;
  for (int i = 0; i < n; i++) {
    if (arr[i] % 2 == 1) {
      odd.push_back(arr[i]);
    } else {
      even.push_back(arr[i]);
    }
  }
  sort(odd.begin(), odd.end());
  sort(even.begin(), even.end());
  int len = min(odd.size(), even.size());
  long long res = 0;
  if (len == odd.size()) {
    len++;
    int k = even.size() - len;
    for (int i = 0; i < (k); i++) {
      res += (even[i]);
    }
  } else {
    len++;
    int k = odd.size() - len;
    for (int i = 0; i < (k); i++) {
      res += (odd[i]);
    }
  }
  cout << res << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  t = 1;
  while (t--) {
    solve();
  }
}
