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

public class Main {

    private static InputReader in;
    private static OutputWriter out;

    public static void main(String[] args) {
        in = new InputReader(System.in);
        out = new OutputWriter(System.out);

        int testcase = 1;

        while (testcase-- > 0) {
            solve();
        }

        out.flush();

        in.close();
        out.close();
    }

    private static void solve() {
        int n = in.nextInt();
        List<Integer> evens = new ArrayList<>();
        List<Integer> odds = new ArrayList<>();

        for (int j = 0; j < n; j++) {
            int a = in.nextInt();

            if(a % 2 == 0){
                evens.add(a);
            }else{
                odds.add(a);
            }
        }

        //Collections.sort(evens);
        evens.sort(Collections.reverseOrder());
        odds.sort(Collections.reverseOrder());
        //Collections.sort(odds);

        int sum = 0;

        if(evens.size() > odds.size()){
            for(int i = odds.size() + 1; i < evens.size();i++){
                sum += evens.get(i);
            }
        }else{
            for(int i = evens.size() + 1; i < odds.size();i++){
                sum += odds.get(i);
            }
        }

        out.println(sum);
    }

    private static String stringSort(String s) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        return new String(chars);
    }

    private static int getCharFrequency(String a, char c) {
        int count = 0;
        for (int i = 0; i < a.length() - 1; i++) {
            if(a.charAt(i) == c){
                count++;
            }
        }

        return count;
    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();

            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }

            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();

            while (isSpaceChar(c))
                c = read();

            int sgn = 1;

            if (c == '-') {
                sgn = -1;
                c = read();
            }

            int res = 0;

            res = (int) getResult(c, res);

            return res * sgn;
        }

        public int[] nextIntArray(int arraySize) {
            int array[] = new int[arraySize];

            for (int i = 0; i < arraySize; i++)
                array[i] = nextInt();

            return array;
        }

        public long nextLong() {
            int c = read();

            while (isSpaceChar(c))
                c = read();

            int sign = 1;

            if (c == '-') {
                sign = -1;

                c = read();
            }

            long result = 0;

            result = getResult(c, result);

            return result * sign;
        }

        private long getResult(int c, long result) {
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();

                result *= 10;
                result += c & 15;

                c = read();
            } while (!isSpaceChar(c));
            return result;
        }

        public long[] nextLongArray(int arraySize) {
            long array[] = new long[arraySize];

            for (int i = 0; i < arraySize; i++)
                array[i] = nextLong();

            return array;
        }

        public float nextFloat() // problematic
        {
            float result, div;
            byte c;

            result = 0;
            div = 1;
            c = (byte) read();

            while (c <= ' ')
                c = (byte) read();

            boolean isNegative = (c == '-');

            if (isNegative)
                c = (byte) read();

            do {
                result = result * 10 + c - '0';
            } while ((c = (byte) read()) >= '0' && c <= '9');

            if (c == '.')
                while ((c = (byte) read()) >= '0' && c <= '9')
                    result += (c - '0') / (div *= 10);

            if (isNegative)
                return -result;

            return result;
        }

        public double nextDouble() // not completely accurate
        {
            double ret = 0, div = 1;
            byte c = (byte) read();

            while (c <= ' ')
                c = (byte) read();

            boolean neg = (c == '-');

            if (neg)
                c = (byte) read();

            do {
                ret = ret * 10 + c - '0';
            } while ((c = (byte) read()) >= '0' && c <= '9');

            if (c == '.')
                while ((c = (byte) read()) >= '0' && c <= '9')
                    ret += (c - '0') / (div *= 10);

            if (neg)
                return -ret;

            return ret;
        }

        public String next() {
            int c = read();

            while (isSpaceChar(c))
                c = read();

            StringBuilder res = new StringBuilder();

            do {
                res.appendCodePoint(c);

                c = read();
            } while (!isSpaceChar(c));

            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String nextLine() {
            int c = read();

            StringBuilder result = new StringBuilder();

            do {
                result.appendCodePoint(c);

                c = read();
            } while (!isNewLine(c));

            return result.toString();
        }

        public boolean isNewLine(int c) {
            return c == '\n';
        }

        public void close() {
            try {
                stream.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

    }

    static class OutputWriter {
        private PrintWriter writer;

        public OutputWriter(OutputStream stream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(
                    stream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void println(int x) {
            writer.println(x);
        }

        public void print(int x) {
            writer.print(x);
        }

        public void println(int array[], int size) {
            for (int i = 0; i < size; i++)
                println(array[i]);
        }

        public void print(int array[], int size) {
            for (int i = 0; i < size; i++)
                print(array[i] + " ");
        }

        public void println(long x) {
            writer.println(x);
        }

        public void print(long x) {
            writer.print(x);
        }

        public void println(long array[], int size) {
            for (int i = 0; i < size; i++)
                println(array[i]);
        }

        public void print(long array[], int size) {
            for (int i = 0; i < size; i++)
                print(array[i]);
        }

        public void println(float num) {
            writer.println(num);
        }

        public void print(float num) {
            writer.print(num);
        }

        public void println(double num) {
            writer.println(num);
        }

        public void print(double num) {
            writer.print(num);
        }

        public void println(String s) {
            writer.println(s);
        }

        public void print(String s) {
            writer.print(s);
        }

        public void println() {
            writer.println();
        }

        public void printSpace() {
            writer.print(" ");
        }

        public void flush() {
            writer.flush();
        }

        public void close() {
            writer.close();
        }

    }

}