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.awt.*;
import java.io.*;
import java.math.BigInteger;
import java.nio.charset.StandardCharsets;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        FastScanner in = new FastScanner();
        Task solver = new Task();
        solver.solve(in);
        in.close();
    }

    static class Task {
        public void solve(FastScanner in) {
            int n = in.nextInt(), x;

            ArrayList<Integer> odd = new ArrayList<>(), even = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                x = in.nextInt();
                if (x % 2 == 0) {
                    even.add(x);
                } else {
                    odd.add(x);
                }
            }

            Collections.sort(odd);
            Collections.sort(even);

            int sum = 0;
            if (odd.size() < even.size()) {
                for (int i = 0; i < even.size() - odd.size() - 1; i++) {
                    sum += even.get(i);
                }
            } else {
                for (int i = 0; i < odd.size() - even.size() - 1; i++) {
                    sum += odd.get(i);
                }
            }
            System.out.print(sum);
        }
    }




    // $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
    public static class FastScanner {
        final private int BUFFER_SIZE = 4096;
        private InputStreamReader in;
        private char[] buffer;
        private int bufferPointer, bytesRead;

        public FastScanner() {
            in = new InputStreamReader(System.in, StandardCharsets.UTF_8);
            buffer = new char[BUFFER_SIZE];
            bufferPointer = 0;
            bytesRead = 0;
        }

        public FastScanner(String name) {
            try {
                in = new InputStreamReader(new FileInputStream(name), StandardCharsets.UTF_8);
            } catch (Exception e) {
                e.printStackTrace();
            }
            buffer = new char[BUFFER_SIZE];
            bufferPointer = 0;
            bytesRead = 0;
        }

        private void fillBuffer() {
            bufferPointer = 0;
            try {
                while ((bytesRead = in.read(buffer)) == 0) {}
            } catch (Exception e) {
                e.printStackTrace();
            }
            if (bytesRead == -1)
                buffer[0] = 0;
        }

        private char next() {
            if (bufferPointer >= bytesRead) {
                fillBuffer();
            }
            return buffer[bufferPointer++];
        }

        public boolean hasNext() {
            if (bufferPointer >= bytesRead) {
                fillBuffer();
                return (bytesRead != -1);
            }
            return true;
        }

        public String nextLine() {
            try {
                StringBuilder now = new StringBuilder();
                char c;
                while (true) {
                    c = next();
                    if (c == 0 || c == '\n') {
                        break;
                    }
                    now.append(c);
                }
                return now.toString();
            } catch (Exception e) {
                e.printStackTrace();
                return "";
            }
        }

        private int convert(StringBuilder s) {
            try {
                return Integer.parseInt(s.toString());
            } catch (IndexOutOfBoundsException e) {
                e.printStackTrace();
                return 0;
            }
        }

        public ArrayList<Integer> nextLineAsIntegers() {
            try {
                String inp = nextLine();
                StringBuilder now = new StringBuilder();
                ArrayList<Integer> res = new ArrayList<>();

                for (int i = 0; i < inp.length(); i++) {
                    if (!(Character.isDigit(inp.charAt(i)) || inp.charAt(i) == '-')) {
                        if (now.length() > 0) {
                            res.add(convert(now));
                            now.delete(0, now.length());
                        }
                    } else {
                        now.append(inp.charAt(i));
                    }
                }
                if (now.length() > 0) {
                    res.add(convert(now));
                }
                return res;
            } catch (Exception e) {
                e.printStackTrace();
                return new ArrayList<>();
            }
        }

        public ArrayList<String> nextLineAsWords() {
            ArrayList<String> res = new ArrayList<>();

            try {
                StringBuffer now = new StringBuffer();
                String inp = nextLine();

                for (int i = 0; i < inp.length(); i++) {
                    if (!(Character.isLetter(inp.charAt(i)) || Character.getType(inp.charAt(i)) == Character.DASH_PUNCTUATION || inp.charAt(i) == '\'')) {
                        if (now.length() == 0) {
                            continue;
                        }
                        String cur = now.toString().toLowerCase();
                        res.add(cur);
                        now.delete(0, now.length());
                    } else {
                        now.append(inp.charAt(i));
                    }
                }
                if (now.length() > 0) {
                    String cur = now.toString().toLowerCase();
                    res.add(cur);
                }
            } catch (Exception e) {
                e.printStackTrace();
            }
            return res;
        }

        public String nextString() {
            while(true) {
                char c = next();
                if (!Character.isWhitespace(c)) {
                    bufferPointer--;
                    break;
                }
            }
            try {
                StringBuilder now = new StringBuilder();
                char c;
                while (true) {
                    c = next();
                    if (c == 0 || Character.isWhitespace(c)) {
                        break;
                    }
                    now.append(c);
                }
                return now.toString();
            } catch (Exception e) {
                e.printStackTrace();
                return "";
            }
        }

        public int nextInt() {
            try {
                int sign = 1, res = 0;
                char c;
                while (true) {
                    c = next();
                    if (!Character.isWhitespace(c)) {
                        break;
                    }
                }
                if (c == '-') {
                    sign = -1;
                    c = next();
                }
                while (Character.isDigit(c)) {
                    res = res * 10 + (int) (c - '0');
                    c = next();
                }
                bufferPointer--;
                if (sign == 1) {
                    return res;
                } else {
                    return -res;
                }
            } catch(Exception e) {
                e.printStackTrace();
                return 0;
            }
        }

        public long nextLong() {
            try {
                long sign = 1l, res = 0l;
                char c;
                while (true) {
                    c = next();
                    if (!Character.isWhitespace(c)) {
                        break;
                    }
                }
                if (c == '-') {
                    sign = -1l;
                    c = next();
                }
                while (Character.isDigit(c)) {
                    res = res * 10l + (long) (c - '0');
                    c = next();
                }
                bufferPointer--;
                if (sign == 1l) {
                    return res;
                } else {
                    return -res;
                }
            } catch(Exception e) {
                e.printStackTrace();
                return 0l;
            }
        }

        public double nextDouble() {
            double res = 0.0, div = 1.0;
            char c;
            while (true) {
                c = next();
                if (!Character.isWhitespace(c)) {
                    break;
                }
            }
            boolean sign = (c == '-');
            if (sign)
                c = next();

            do {
                res = res * 10.0 + (c - '0');
            }
            while ((c = next()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = next()) >= '0' && c <= '9') {
                    res += (c - '0') / (div *= 10.0);
                }
            }

            if (sign)
                return -res;
            return res;
        }

        public void close() {
            try {
                in.close();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }
}
