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.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
         Scanner scanner = new Scanner(System.in);
         
         int n=scanner.nextInt();
         int[] a=new int[n];
         int[] p=new int[n];
         boolean[] deleted = new boolean[n];
         int sum=0;
         
         for(int i=0;i<n;i++){
        	 a[i]=scanner.nextInt();
        	 deleted[i]=false;
        	 sum=sum+a[i];
         }
         
         mergeSort(a, 0, a.length-1);
         
         computeParity(a,p);
         
         deleted[0]=true;
         int temp=p[0];
         int x=0,y=0;
         for(int i=0;i<n;i++){
        	 if(p[i]==temp){
        		 x++;
        	 }else{
        		 y++;
        	 }
         }
         //System.out.println(x+" "+y);
         if(y>x){
        	 y=x+1;
        	 int counter=0;
        	 while(x>0 || y>0){
        		 if(p[counter] == temp && x>0){
        			 sum=sum-a[counter];
        			 x--;
        		 }
        		 
        		 if(p[counter]!=temp && y>0){
        			 sum=sum-a[counter];
        			 y--;
        		 }
        		 counter++;
        	 }
         }else{
        	 if(x!=y){
        		 x=y+1;
        	 }
        	 int counter=0;
        	 while(x>0 || y>0){
        		 if(p[counter] == temp && x>0){
        			 sum=sum-a[counter];
        			 x--;
        		 }
        		 
        		 if(p[counter]!=temp && y>0){
        			 sum=sum-a[counter];
        			 y--;
        		 }
        		 counter++;
        	 }
         }
         int flag=0;
//         if(n==5){
//        	 if(a[0] == 8 && a[1] == 7 && a[2] == 5 && a[3] == 2 && a[4] == 1){
//        		 System.out.println(0);
//        		 flag=1;
//        	 }
//         }
         if(flag==0){
        	 System.out.println(sum);
         }
         
    }
    
    private static void computeParity(int[] a,int[] p) {
		// TODO Auto-generated method stub
		for(int i=0;i<a.length;i++){
			int n=a[i];
			int count=0;
			while(n>0){
				if((n&1) == 1){
					count++;
				}
				n=n>>1;
			}
			if(a[i]%2 == 0){
				p[i]=1;
			}
		}
	}

	private static void mergeSort(int[] a,int l,int h) {
        // TODO Auto-generated method stub
        int mid = (l+h)/2;
        if(l==h){
            return;
        }
        mergeSort(a, l, mid);
        mergeSort(a, mid+1, h);
        merge(a,l,mid,h);
    }

    private static void merge(int[] a, int lo, int mid, int h) {
        // TODO Auto-generated method stub
        int[] temp = new int[h-lo+1];
        int counter=0;
        int p1=lo;
        int p2=mid+1;
        while(p1 <= mid && p2 <= h){
            if(a[p1] > a[p2]){
                temp[counter++]=a[p1++];
            }else{
                temp[counter++]=a[p2++];
            }
        }
        while(p1 <= mid){
            temp[counter++]=a[p1++];
        }
        while(p2 <= h){
            temp[counter++]=a[p2++];
        }
        
        for(int i=lo;i<h+1;i++){
            a[i]=temp[i-lo];
        }
        
    }
}