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.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.*;

import javax.swing.text.InternationalFormatter;

import java.math.*;

import org.omg.CORBA.Any;

public class template {

	static int n = 0, m = 0, k = 0;

	public static void main(String[] args) throws IOException {
		Scanner scn = new Scanner(System.in);

		   int n=scn.nextInt();
		    ArrayList<Integer> o=new ArrayList<>();
		    ArrayList<Integer> e=new ArrayList<>();
		    
		    for(int i=0; i<n; i++){
		    	int x=scn.nextInt();
		    	
		    	 if(x%2 == 0)
		    		 e.add(x);
		    	 else
		    		 o.add(x);
		    }
		    
            Collections.sort(o, Collections.reverseOrder()); Collections.sort(e, Collections.reverseOrder());
            long ans=0;
            
            
            if(e.size() == 0){
            	long p=0;
            	for(int i=1; i<o.size(); i++)
            		p+=o.get(i);
            	
            	System.out.println(p);
            	
            }
            
            else if(o.size() == 0){
            	long p=0;
            	for(int i=1; i<e.size(); i++)
            		p+=e.get(i);
            	
            	System.out.println(p);
            	
            }
            
            else if(Math.abs(e.size()-o.size())<=1)
		    	System.out.println(0);
		    
		    else{
		    	
		    	    if(o.size() < e.size()){
		    	    	int d=o.size();
		    	    	
		    	    	for(int i=0; i<e.size(); i++){
		    	    		  if(d==-1)
		    	    			  ans+=e.get(i);
		    	    		  else
		    	    			  d--;
		    	    	}
		    	    }
		    	    
		    	    else{
		    	    	 int d=e.size();
		    	    	 for(int i=0; i<o.size(); i++){
		    	    		  if(d==-1)
		    	    			  ans+=o.get(i);
		    	    		  else
		    	    			  d--;
		    	    	}
		    	    }
		    	    
		    	    
		    	    System.out.println(ans);
		    }
		}
	}

	//



// _________________________TEMPLATE_____________________________________________________________

class pair implements Comparable<pair> {
	int rating;
	int div;

	pair(int l, int b) {
		rating = l;
		div = b;
	}

	@Override
	public int compareTo(pair o) {

		return this.rating - o.rating;
	}

	public static void printarray(long[] dp1) {
		for (long i : dp1)
			System.out.print(i + " ");
		System.out.println();
	}

	public static void inputarray(long[] a, int n, Reader scn) throws IOException {
		for (int i = 0; i < n; i++)
			a[i] = scn.nextLong();
	}

	public static class Reader {
		final private int BUFFER_SIZE = 1 << 16;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;

		public Reader() {
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public Reader(String file_name) throws IOException {
			din = new DataInputStream(new FileInputStream(file_name));
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public String readLine() throws IOException {
			byte[] buf = new byte[100000 + 1]; // line length
			int cnt = 0, c;
			while ((c = read()) != -1) {
				if (c == '\n')
					break;
				buf[cnt++] = (byte) c;
			}
			return new String(buf, 0, cnt);
		}

		public int nextInt() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (neg)
				return -ret;
			return ret;
		}

		public long nextLong() throws IOException {
			long ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}

		public double nextDouble() throws IOException {
			double ret = 0, div = 1;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();

			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (c == '.') {
				while ((c = read()) >= '0' && c <= '9') {
					ret += (c - '0') / (div *= 10);
				}
			}

			if (neg)
				return -ret;
			return ret;
		}

		private void fillBuffer() throws IOException {
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1)
				buffer[0] = -1;
		}

		private byte read() throws IOException {
			if (bufferPointer == bytesRead)
				fillBuffer();
			return buffer[bufferPointer++];
		}

		public void close() throws IOException {
			if (din == null)
				return;
			din.close();
		}
	}

	// private static void rem(HashMap<Integer, Integer> hm) {
	//
	// Iterator<Map.Entry<Integer, Integer>> itr = hm.entrySet().iterator();
	// ArrayList<Integer> p=new ArrayList<>();
	//
	//
	// while(itr.hasNext()){
	// Map.Entry<Integer, Integer> entry = itr.next();
	// p.add(entry.getKey());
	//
	// }
	//
	//
	// for(int i:p){
	//
	// if(hm.get(i)>1)
	// hm.put(i, hm.get(i)-1);
	// else
	// hm.remove(i);
	// }
	// }

}
