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 Jobeel;
import java.util.*;
import java.io.*;
import java.lang.*;
import java.math.*;
import java.util.Map.*;
public class codeforces {
	public static void main(String [] args) throws IOException, InterruptedException {
	    InputReader sc=new InputReader(System.in);
	   LinkedList<Integer> odd=new LinkedList<>();
	   LinkedList<Integer> even=new LinkedList<>();
	    int x=sc.nextInt();
	    for(int i=0;i<x;i++) {
	    	int y=sc.nextInt();
	    	if(y%2==0) even.add(y);
	    	else odd.add(y);
	    }
	    //pw.println(even+" "+odd);
	    Collections.sort(odd); Collections.sort(even);
	    
	 //  pw.println(even+" "+odd);
	    boolean f;
	    if(even.size()>odd.size())
	        f=true;
	    else  f=false;
	    while(!odd.isEmpty() && !even.isEmpty()) {
	    	if(f) {
	    	even.pollLast(); f=!f;
	    	}else {
				f=!f;
			odd.pollLast();
	    	}
	    }
	 //   pw.println(even+" "+odd);
	    if(f && !even.isEmpty()) even.pollLast();
	    if( !odd.isEmpty() && !f) odd.pollLast();
	   // 
	    long sum=0;
	    while(!odd.isEmpty()) sum+=odd.pollFirst();
	    while(!even.isEmpty()) sum+=even.pollLast();
	    pw.print(sum);
	    pw.flush();
		pw.close();
	}
      static class pair implements Comparable<pair>{
    		String  name; int x,y,z ;
    		
    		
    		public pair (int x,int y) {
    			this.x=x; this.y=y; 
    		}
    		public int compareTo(pair o) {
    			if(x!=o.x) return x-o.x;
    			return y-o.y;
    		}
    		public String toString() {
    			return x+" "+y;
    		}
    	}
      static int [] size,arr;
    	static long inv=(long)2e18;
    	static long M=(long)1e9+9,P=999983;
    	static HashSet<StringBuilder> set_1;
    	static TreeSet<Long> set; 
    	
    	static int fix(int a,int k) {          // turn -% to +%
    		return (a%k+k)%k;
    	}
        static void solveBruteForece(int index , int mask,int [] arr) {
    		if(index==arr.length) {
    			long sum=1;
    			for(int i=0;i<arr.length;i++) {
    				if((mask & 1<<i)!=0) sum*=arr[i];
    				
    			}
    			for(int i=0;i<arr.length;i++) {
    				if(sum%arr[i]!=0) return ;
    			}
    			inv=Math.min(inv, sum);
    			return;
    		}
    		solveBruteForece(index+1,mask | 1<<index,arr) ;solveBruteForece(index+1,mask,arr);
    	}
    	public static int find(int i) {
    		if(arr[i]==i) return i;
    		else {
    			int result=find(arr[i]);
    			arr[i]=result;
    			return result;
    		}
    	}
    public static void union(int u,int v) {
    		int root_u=find(u);
    		int root_v=find(v);
    		if (root_u==root_v) return;
    		else if(size[root_u]>size[root_v]) {
    			size[root_u]+=size[root_v];
    			arr[root_v]=root_u;
    		}else  {
    			size[root_v]+=size[root_u];
    			arr[root_u]=root_v;
    		}
    	}
        static int search(int x,int [] arr) {
        	int low=0,high=arr.length-1,ans=-1;
        	while(low<=high) {
        		int mid=(low+high)>>1;
        	   if(arr[mid]==x) { ans=mid; break;}
        	   else if(arr[mid]>x) high=mid-1;
        	   else low=mid+1;
        	}
        	return ans;
        }
       static  long gcd(long a, long b) 
        { 
            if (b == 0) 
                return a; 
            return gcd(b, a % b);  
              
        } 
       public static long largestDivisor(long n){
    	   long divisor = 0;
    	   long  w=n>>1;
    	   for (int i = 1; i <= w; i++)
    	       if (n % i == 0) 
    	           divisor = i;
   
    	   return divisor; 
    	}
      static int min (int x,int y,int z) {return Math.min(Math.min(x, y), z);}
      static long min (long x,long y,long z) {return Math.min(Math.min(x, y), z);}
      static int max (int x,int y,int z) {return Math.max(Math.max(x, y), z);}
      static long max (long x,long y,long z) {return Math.max(Math.max(x, y), z);}
  	
   
  	static 	PrintWriter pw=new PrintWriter(System.out);
  	
  	static class InputReader  {
  		 
  		private InputStream in;
  		private byte[] buffer = new byte[1024];
  		private int curbuf;
  		private int lenbuf;
   
  		public InputReader(InputStream in) {
  			this.in = in;
  			this.curbuf = this.lenbuf = 0;
  		}
   
  		public boolean hasNextByte() {
  			if (curbuf >= lenbuf) {
  				curbuf = 0;
  				try {
  					lenbuf = in.read(buffer);
  				} catch (IOException e) {
  					throw new InputMismatchException();
  				}
  				if (lenbuf <= 0)
  					return false;
  			}
  			return true;
  		}
   
  		private int readByte() {
  			if (hasNextByte())
  				return buffer[curbuf++];
  			else
  				return -1;
  		}
   
  		private boolean isSpaceChar(int c) {
  			return !(c >= 33 && c <= 126);
  		}
   
  		private void skip() {
  			while (hasNextByte() && isSpaceChar(buffer[curbuf]))
  				curbuf++;
  		}
   
  		public boolean hasNext() {
  			skip();
  			return hasNextByte();
  		}
   
  		public String next() {
  			if (!hasNext())
  				throw new NoSuchElementException();
  			StringBuilder sb = new StringBuilder();
  			int b = readByte();
  			while (!isSpaceChar(b)) {
  				sb.appendCodePoint(b);
  				b = readByte();
  			}
  			return sb.toString();
  		}
   
  		public int nextInt() {
  			if (!hasNext())
  				throw new NoSuchElementException();
  			int c = readByte();
  			while (isSpaceChar(c))
  				c = readByte();
  			boolean minus = false;
  			if (c == '-') {
  				minus = true;
  				c = readByte();
  			}
  			int res = 0;
  			do {
  				if (c < '0' || c > '9')
  					throw new InputMismatchException();
  				res = res * 10 + c - '0';
  				c = readByte();
  			} while (!isSpaceChar(c));
  			return (minus) ? -res : res;
  		}
   
  		public long nextLong() {
  			if (!hasNext())
  				throw new NoSuchElementException();
  			int c = readByte();
  			while (isSpaceChar(c))
  				c = readByte();
  			boolean minus = false;
  			if (c == '-') {
  				minus = true;
  				c = readByte();
  			}
  			long res = 0;
  			do {
  				if (c < '0' || c > '9')
  					throw new InputMismatchException();
  				res = res * 10 + c - '0';
  				c = readByte();
  			} while (!isSpaceChar(c));
  			return (minus) ? -res : res;
  		}
   
  		public double nextDouble() {
  			return Double.parseDouble(next());
  		}
   
  		public int[] nextIntArray(int n) {
  			int[] a = new int[n];
  			for (int i = 0; i < n; i++)
  				a[i] = nextInt();
  			return a;
  		}
   
  		public long[] nextLongArray(int n) {
  			long[] a = new long[n];
  			for (int i = 0; i < n; i++)
  				a[i] = nextLong();
  			return a;
  		}
   
  	}
      static TreeSet<Long> printDivisors(long n) 
      { 
    	  TreeSet<Long> set=new TreeSet<>();
          for (long i=1; i<=Math.sqrt(n); i++) 
          { 
              if (n%i==0) 
              { 
                  if (n/i == i) 
                     set.add(i);
         
                  else {set.add(i); set.add(n/i);} 
              } 
          } 
          return set;
      } 
  	}