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.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Seg {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		int n = sc.nextInt();
		int[] a = sc.nextArr(n);
		int e = 0;
		int o = 0;
		for (int i = 0; i < a.length; i++) {
			if (a[i] % 2 == 0)
				e++;
			else
				o++;
		}
		int[] ae = new int[e];
		int[] oe = new int[o];
		int j = 0;
		int k = 0;
		for (int i = 0; i < a.length; i++) {
			if (a[i] % 2 == 0) {
				ae[j] = a[i];
				j++;
			} else {
				oe[k] = a[i];
				k++;
			}
		}
		Arrays.sort(ae);
		Arrays.sort(oe);
		
		// Cases
		int sum1 = 0;
		int sum2 = 0;
		for (int i = 0; i < ae.length; i++)
			sum1 += ae[i]; // even
		for (int i = 0; i < oe.length; i++) {
			sum2 += oe[i]; // odd
		}
		if (e == 0) {
			System.out.println(sum2 - oe[oe.length - 1]);
		} else if (o == 0) {
			System.out.println(sum1 - ae[ae.length - 1]);
		} else if (e == 0) {
			System.out.println(0);

		} else {
			sum1 = 0;
			sum2 = 0;
			if (e > o) {
				o++;
				for(int i =0; i<ae.length-o; i++) {
					sum1+=ae[i];
				}System.out.println(sum1);

			}else {
				e++;
				for(int i =0; i<oe.length-e; i++) {
					sum2+=oe[i];
				}System.out.println(sum2);
			}

		}

		pw.flush();
		pw.close();
	}

	/**
	 *
	 * Fixed Window Find the max sum subarray of a fixed size K
	 *
	 * Example input: [4, 2, 1, 7, 8, 1, 2, 8, 1, 0]
	 *
	 */
	public static int findMaxSumSubarray(int[] arr, int k) {
		int maxValue = Integer.MIN_VALUE;
		int currentRunningSum = 0;
		for (int i = 0; i < arr.length; i++) {
			currentRunningSum += arr[i];
			if (i >= k - 1) {
				maxValue = Math.max(maxValue, currentRunningSum);
				currentRunningSum -= arr[i - (k - 1)]; // Akher element fl 3 bto3 el K
			}
		}
		return maxValue;
	}

	// Dynamic Window
	public static int smallestSubarray(int targetSum, int[] arr) {
		int minWindowSize = Integer.MAX_VALUE;
		int currentWindowSum = 0;
		int windowStart = 0;
		for (int windowEnd = 0; windowEnd < arr.length; windowEnd++) {
			currentWindowSum += arr[windowEnd];
			while (currentWindowSum >= targetSum) {
				minWindowSize = Math.min(minWindowSize, windowEnd - windowStart + 1);
				currentWindowSum -= arr[windowStart];
				windowStart++;
			}
		}
		return minWindowSize;
	}

	// better solution for less steps
	// public static int dfs(int node) {
	// visited[node] = true;
	// int c = 1;
	// for (int i : adjList[node]) {
	// if (!visited[i]) {
	// c += dfs(i);
	// }
	// }
	// return c;
	// Getting last occur of element
	// public static int binarySearch(int low, int n, int high) {
	// low = 0;
	// high = n - 1;
	// while (low <= high) {
	// int mid = (low + high) / 2;
	// if (x >= a[mid]) {
	// if (x == a[mid]) {
	// ans = mid;
	// }
	// low = mid + 1;
	//
	// } else if (a[mid] > x) {
	// high = mid - 1;
	// }
	// }
	//
	// }
	public static int gcdFast(int x, int y) {
		if (y == 0) {
			return x;
		} else {
			return gcdFast(y, x % y);
		}
	}

	public static class Pair implements Comparable<Pair> {
		int a, b;

		public Pair(int a, int b) {
			this.a = a;
			this.b = b;
		}

		public int compareTo(Pair A) {
			return this.a > A.a ? 1 : -1; // sorting ascending
		}
	}

	public static int findLength(String str, int k) {
		int windowStart = 0, maxLength = -1;
		HashMap<Character, Integer> hs = new HashMap<Character, Integer>();
		for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
			char rightChar = str.charAt(windowEnd);
			hs.put(rightChar, hs.getOrDefault(rightChar, 0) + 1); // Increasing its value by 1 and if it have no value
																	// just its zero and add 1
			while (hs.size() > k) {
				char leftChar = str.charAt(windowStart);
				hs.put(leftChar, hs.get(leftChar) - 1);
				if (hs.get(leftChar) == 0) {
					hs.remove(leftChar);
				}
				windowStart++;
			}
			maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
		}
		return maxLength;
	}

	public static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(String file) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(file));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

		public int[] nextArr(int n) throws IOException {
			int arr[] = new int[n];
			for (int i = 0; i < n; i++)
				arr[i] = nextInt();
			return arr;
		}
	}
}