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
import java.util.*;

public class StackBracket {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] ar = new int[n];
        long sum=0;
        List<Integer> even=new ArrayList<>();
        List<Integer> odd=new ArrayList<>();
        for(int i=0;i<n;i++){
            ar[i]=sc.nextInt();
            sum+=ar[i];
            if(ar[i]%2==0){
                even.add(ar[i]);
            }else {
                odd.add(ar[i]);
            }
        }
        Collections.sort(even);
        Collections.sort(odd);
        int c=0;
        int evep=even.size()-1;
        int oddp=odd.size()-1;
        long sumc=sum;
        while (true){
            if(c%2==0){
                if(evep>=0){
                    sumc-=even.get(evep);
                    evep--;
                }else {
                    break;
                }

            }else {
                if(oddp>=0){
                    sumc-=odd.get(oddp);
                    oddp--;
                }else {
                    break;
                }

            }
            c++;
        }
        c=0;
        evep=even.size()-1;
        oddp=odd.size()-1;
        long sumc1=sum;
        while (true){
            if(c%2!=0){
                if(evep>=0){
                    sumc1-=even.get(evep);
                    evep--;
                }else {
                    break;
                }

            }else {
                if(oddp>=0){
                    sumc1-=odd.get(oddp);
                    oddp--;
                }else {
                    break;
                }

            }
            c++;
        }
        System.out.println(Math.min(sumc,sumc1));


    }

    public static boolean strive(String s) {
        Stack<Character> stack = new Stack<>();
        stack.push(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            char ch1 = s.charAt(i);
            if (ch1 == ')') {
                if (!stack.isEmpty() && stack.peek() == '(') {
                    stack.pop();
                } else {
                    return false;
                }
            } else {
                stack.push('(');
            }
        }
        /*if(stack.size()!=0){
           // System.out.println("NO");
        }else {
            System.out.println("YES");
        }*/
        return stack.size() == 0;
    }

    public static int getAns(int[] ar, int bigger, int[][] dp, int i, int j) {

        if (i < 0 || j < 0) {
            return 0;
        }


        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        int ans1 = 0, ans2 = 0, ans3 = 0;

        if (ar[i] < bigger) {
            ans1 = 1 + getAns(ar, ar[i], dp, i - 1, j);
            // ans3=1+getAns(ar, ar[i],dp, i - 1,j-1);
        } else {
            ans2 = getAns(ar, bigger, dp, i - 1, j - 1);
        }

        dp[i][j] = Math.max(ans1, ans2);
        return dp[i][j];

    }


    public static long power(long a, long b, long c) {
        long ans = 1;
        while (b != 0) {
            if (b % 2 == 1) {
                ans = ans * a;
                ans %= c;
            }
            a = a * a;
            a %= c;
            b /= 2;
        }
        return ans;
    }

    public static long power1(long a, long b, long c) {
        long ans = 1;
        while (b != 0) {
            if (b % 2 == 1) {
                ans = multiply(ans, a, c);
            }
            a = multiply(a, a, c);
            b /= 2;

        }
        return ans;

    }

    public static long multiply(long a, long b, long c) {
        long res = 0;
        a %= c;
        while (b > 0) {
            if (b % 2 == 1) {
                res = (res + a) % c;
            }
            a = (a + a) % c;
            b /= 2;
        }

        return res % c;

    }

    public static long totient(long n) {
        long result = n;
        for (long i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                //sum=sum+2*i;
                while (n % i == 0) {
                    n /= i;
                    // sum=sum+n;
                }
                result -= result / i;

            }
        }
        if (n > 1) {
            result -= result / n;

        }
        return result;
    }


    public static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }

    public static boolean[] primes(int n) {
        boolean[] p = new boolean[n + 1];
        p[0] = false;
        p[1] = false;
        for (int i = 2; i <= n; i++) {
            p[i] = true;
        }

        for (int i = 2; i * i <= n; i++) {
            if (p[i]) {
                for (int j = i * i; j <= n; j += i) {
                    p[j] = false;
                }
            }

        }
        return p;
    }

    static int val(char c) {
        if (c >= '0' && c <= '9')
            return (int) c - '0';
        else
            return (int) c - 'A' + 10;
    }

    // Function to convert a
// number from given base
// 'b' to decimal
    static int toDeci(String str,
                      int base) {
        int len = str.length();
        int power = 1; // Initialize
        // power of base
        int num = 0; // Initialize result
        int i;

        // Decimal equivalent is
        // str[len-1]*1 + str[len-2] *
        // base + str[len-3]*(base^2) + ...
        for (i = len - 1; i >= 0; i--) {
            // A digit in input number
            // must be less than
            // number's base
            if (val(str.charAt(i)) >= base) {
                System.out.println("Invalid Number");
                return -1;
            }

            num += val(str.charAt(i)) * power;
            power = power * base;
        }

        return num;
    }
}
	 	    	   	   	    		 			 				