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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;

public class ParityAlternatedDeletionsCodeforces {
	  static class FastReader {
	        BufferedReader br;
	        StringTokenizer st;
	 
	        public FastReader()
	        {
	            br = new BufferedReader(
	                new InputStreamReader(System.in));
	        }
	 
	        String next()
	        {
	            while (st == null || !st.hasMoreElements()) {
	                try {
	                    st = new StringTokenizer(br.readLine());
	                }
	                catch (IOException e) {
	                    e.printStackTrace();
	                }
	            }
	            return st.nextToken();
	        }
	 
	        int nextInt() { return Integer.parseInt(next()); }
	 
	        long nextLong() { return Long.parseLong(next()); }
	 
	        double nextDouble()
	        {
	            return Double.parseDouble(next());
	        }
	 
	        String nextLine()
	        {
	            String str = "";
	            try {
	                str = br.readLine();
	            }
	            catch (IOException e) {
	                e.printStackTrace();
	            }
	            return str;
	        }
	    }
	 

	public static void main(String[] args) {
		FastReader s=new FastReader();
	    int n=s.nextInt();
        
        int a[]=new int[n];
       
        for(int i=0;i<n;++i)
        a[i]=s.nextInt();

         int cnte=0,cnto=0,sum=0;

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

         for(int i=0;i<n;++i){
             if(a[i]%2==0)
             cnte++;
             else
             cnto++;
         }

         if((cnte==cnto) || ((cnte-cnto)==1) ||((cnto-cnte)==1))
         System.out.println(0);

         else{
               Arrays.sort(a);
               int i=n-1;
               int j=n-1;
               if(cnte>cnto){
                int h=cnto+1;
                while(cnto >0){
                  if(a[i]%2!=0){
                    sum -=a[i];
                    cnto--;
                  }
                   
                    i--;
                }
                
                while(h >0){
                    if(a[j]%2==0){
                        sum -=a[j];
                        h--;
                    }
                      
                    j--;
                  }
                  System.out.println(sum);
               }
               else{
                int h=cnte+1;
                while(cnte>0){
                    if(a[i]%2==0){
                        sum -=a[i];
                        cnte--;
                    } 
                       i--;
                  }
                 
                  while(h >0){
                      if(a[j]%2!=0){
                        sum -=a[j];
                        h--;
                      }
                         j--;
                    }
                    System.out.println(sum);
                 }
                 
               }
         }
	}
