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.lang.*;
import java.util.*;
public class plmin {
    public static void main(String[] args) 
    {
      Scanner sc=new Scanner(System.in);
      int n=sc.nextInt(),t=0,sum=0,m=0,m1=0,e=0,o=0;
     // int even[]=new int[n],e=0;
      //int odd[]=new int[n],o=0;
      ArrayList<Integer> even=new ArrayList<Integer>();
      ArrayList<Integer> odd=new ArrayList<Integer>();
      for(int i=0;i<n;i++)
      {
         t=sc.nextInt();
         sum+=t;
          if(t%2==0)
              even.add(t);
              //even[e++]=t;
          else
              odd.add(t);
              //odd[o++]=t;
      }
      int e1=even.size()-1,o1=odd.size()-1;
      Collections.sort(even);
      Collections.sort(odd);
      int p=0;
      //System.out.println(even+" "+odd);
     // System.out.println(sum+" "+e1+" "+o1);
      while(1==1)
      {
          if(p==0)
          {
              if(e1==-1)
                  break;
              m+=even.get(e1--);
              p=1;
             // System.out.println(m+" "+e1+" "+o1);
          }
          else
          {
              if(o1==-1)
                  break;
          m+=odd.get(o1--);
          p=0;
        //  System.out.println(m+" "+e1+" "+o1);
          }
      }
      p=1;
      e1=even.size()-1;o1=odd.size()-1;
      while(1==1)
      {
          if(p==0)
          {
              if(e1==-1)
                  break;
              m1+=even.get(e1--);
              p=1;
             // System.out.println(m1+" "+e1+" "+o1);
          }
          else
          {
              if(o1==-1)
                  break;
          m1+=odd.get(o1--);
          p=0;
        //  System.out.println(m1+" "+e1+" "+o1);
          }
      }
      if(m>m1)
    sum=sum-m;
    else
    sum=sum-m1;
    System.out.println(sum);
    }   
}