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

public class Main {

    public static void main(String[] args) throws Exception {
        StringBuilder out = new StringBuilder();
        int n = in.nextInt();

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

        int e = 0;
        int o = 0;

        boolean startEven = even.size() > odd.size();

        while (true) {
            if (startEven) {
                if (e == even.size()) {
                    break;
                }
                startEven = false;
                e++;
            } else  {
                if(o == odd.size()) {
                    break;
                }
                startEven = true;
                o++;
            }
        }

        long sum = 0;
        while (e != even.size()) {
            sum+= even.get(e);
            e++;
        }

        while (o != odd.size()) {
            sum+= odd.get(o);
            o++;
        }
        System.out.println(sum);

    }


    static class IntegerDisjointSet extends DisjointSet<Integer> {
        public IntegerDisjointSet(int size, int start) {
            for (int i = 0; i < size; i++) {
                add(start++);
            }
        }

        public IntegerDisjointSet(int size) {
            this(size, 0);
        }
    }


    static class DisjointSet<T> {
        Map<T, T> parent;
        Map<T, Integer> rank;

        public DisjointSet() {
            parent = new HashMap<>();
            rank = new HashMap<>();
        }


        public void add(T element) {
            parent.put(element, element);
            rank.put(element, 1);
        }

        @SuppressWarnings("ConstantConditions")
        public void join(T element1, T element2) {
            T parent1 = findParent(element1);
            T parent2 = findParent(element2);

            if (rank.get(parent1) > rank.get(parent2)) {
                rank.compute(parent1, (key, oldVal) -> oldVal + rank.get(parent2));
                parent.put(parent2, parent1);
            } else {
                rank.compute(parent2, (key, oldVal) -> oldVal + rank.get(parent1));
                parent.put(parent1, parent2);
            }
            if (rank.get(parent1).equals(rank.get(parent2))) {
                rank.compute(parent2, (key, oldVal) -> oldVal + 1);
            }
        }

        private T findParent(T element) {
            T parent = this.parent.get(element);
            if (element.equals(parent)) {
                return parent;
            }
            T foundParent = findParent(parent);
            this.parent.put(element, foundParent);
            return foundParent;
        }


        public boolean sameSet(T element1, T element2) {
            T parent1 = findParent(element1);
            T parent2 = findParent(element2);
            return parent1.equals(parent2);
        }

    }


    static class Edge<T> {
        public T source;
        public T destination;
        public int weight;

        public Edge(T source, T destination) {
            this.source = source;
            this.destination = destination;
        }

        public Edge(T source, T destination, int weight) {
            this.source = source;
            this.destination = destination;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "utils.Edge{" +
                    "source=" + source +
                    ", destination=" + destination +
                    ", weight=" + weight +
                    '}';
        }
    }


    static class in {

        private static BufferedReader reader;
        private static StringTokenizer tokenizer;

        static {
            reader = new BufferedReader(
                    new InputStreamReader(System.in));
            tokenizer = new StringTokenizer(" ");
        }

        static void init(InputStream input) {
            reader = new BufferedReader(
                    new InputStreamReader(input));
            tokenizer = new StringTokenizer(" ");
        }

        static String nextLine() throws IOException {
            return reader.readLine();
        }

        static String next() throws IOException {
            while (!tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(
                        reader.readLine());
            }
            return tokenizer.nextToken();
        }

        static boolean hasNext() {
            return tokenizer.hasMoreTokens();
        }

        static int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        static int nextShort() throws IOException {
            return Short.parseShort(next());
        }

        static double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        static long nextLong() throws IOException {
            return Long.parseLong(next());
        }
    }

}