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
//package codforces;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


public class Main {
	
	LinkedList<Integer> adj[];
	int[] respecc_array;
	
	public static void main(String[] args)throws IOException
	{
		Reader.init(System.in);
		int no = Reader.nextInt();
		PriorityQueue<Integer> pque = new PriorityQueue<Integer>();
		int count_odd = 0;
		int count_even =0 ;
		for( int i=0; i<no; i++)
		{
			int x = Reader.nextInt();
			pque.add(x);
			if(x%2==0)
				count_even++;
			else
				count_odd++;
		}
		if(count_even==count_odd)
		{
			System.out.println(0);
		}
		else if(count_even>count_odd)
		{
			int required = count_even - count_odd-1;
			if(required==0)
			{
				System.out.println(0);
				return;
			}
			long sum = 0;
			while(required>=1)
			{
				int top = pque.poll();
				if(top%2==0)
				{
					sum+=top;
					required--;
				}
			}
			System.out.println(sum);
			
		}
		else
		{
			int required = count_odd - count_even-1;
			if(required==0)
			{
				System.out.println(0);
				return;
			}
			long sum = 0 ;
			while(required>=1)
			{
				int top = pque.poll();
				if(top%2!=0)
				{
					required--;
					sum+=top;
				}
			}
			System.out.println(sum);
			
		}
		
		
		
	}
}
class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(
                     new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }

    /** get next word */
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                   reader.readLine() );
        }
        return tokenizer.nextToken();
    }
    
    static long nextLong() throws IOException{
    	return Long.parseLong(next());
    }

    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
	
    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
}