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 javafx.util.Pair;

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        __SolutionBase begin = new __SolutionBase();
        begin.Solve();
    }
}

class __SolutionBase {

    public void Solve() {
        init();
        Solution();
        out.close();
    }

    private final int INF = -1000500;

    private void Solution() {

        int n = readInt();

        int[] a = new int[n];

        for (int i = 0; i < n; i++) a[i] = readInt();

        int[] count = new int[2];

        for (int i = 0; i < n; i++) count[a[i] % 2]++;

        if (count[0] == count[1]) {
            out.println(0);
            return;
        }
        Queue<Integer>[] nums = new Queue[2];
        nums[0] = new PriorityQueue<>((o1, o2) -> -o1.compareTo(o2));
        nums[1] = new PriorityQueue<>((o1, o2) -> -o1.compareTo(o2));

        //1 min, last max

        for (int elem : a) {
            nums[elem % 2].add(elem);
        }


        boolean isWas = false;
        while (count[0] != 0 && count[1] != 0) {
            count[0]--;
            count[1]--;
            nums[0].poll();
            nums[1].poll();
            isWas = true;
        }
        if (isWas) {
            if (nums[0].size() == 0) {
                if (nums[1].size() != 0)
                    nums[1].poll();
            } else if (nums[1].size() == 0) {
                if (nums[0].size() != 0)
                    nums[0].poll();
            } else {
                int zero = nums[0].poll();
                int one = nums[1].poll();

                if (zero > one) {
                    nums[1].add(one);
                } else nums[0].add(zero);

            }
        }else{
            if (nums[0].size() == 0)
                nums[1].poll();
            if (nums[1].size() == 0 )
                nums[0].poll();
        }
        long answer = 0;

        while (nums[0].size() != 0)
            answer += nums[0].poll();

        while (nums[1].size() != 0)
            answer += nums[1].poll();

        out.println(answer);

    }

    /**
     * readLong, readDouble and other are similar
     *
     * @return int type from input
     */
    private int readInt() {
        return Integer.parseInt(readString());
    }

    private long readLong() {
        return Long.parseLong(readString());
    }
    /**
     * Tokens are separated by space or endExclusive of line
     *
     * @return non-empty string token from input (or null if there is no any token)
     */
    private String readString() {
        while (!tok.hasMoreTokens()) {
            String nextLine = readLine();
            if (null == nextLine) return null;
            tok = new StringTokenizer(nextLine);
        }

        return tok.nextToken();
    }

    /**
     * @return whole line from input
     */
    private String readLine() {
        try {
            return in.readLine();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }
    private BufferedReader in;
    private PrintWriter out;
    private StringTokenizer tok = new StringTokenizer(" ");

    /**
     * For local testing I use pair 'input.txt'/'output.txt' in the project root
     */
    private void init() {
        try {
            in = new BufferedReader(new FileReader("lepus.in"));
            out = new PrintWriter("lepus.out");
        } catch (FileNotFoundException e) {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        }
    }
}