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.*;
//import javafx.util.Pair;
public class Solution implements Runnable 
{  
    
    class Pair implements Comparable <Pair>
    {
        long x,y;
        Pair(long x,long y)
        {
            this.x=x;
            this.y=y; 
        }
        public int compareTo(Pair p)
        {
            return Long.compare(x,p.x);
        }
    }
    
    public static void main(String[] args)
    {
        new Thread(null, new Solution(), "rev", 1 << 29).start();
    }

    public void run()
    {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(1,in,out);
        out.close();
    }
    
    class Task
    { 
        
        void solve(int testNumber, InputReader in, PrintWriter out)
        { 
            int n=in.nextInt(),x;
            long sum=0;
            ArrayList <Integer>al0=new ArrayList<>();
            ArrayList <Integer>al1=new ArrayList<>();
            for(int i=0;i<n;i++)
            {
                x=in.nextInt();
                if(x%2==0)
                    al0.add(x);
                else
                    al1.add(x);
            }
            Collections.sort(al0);
            Collections.sort(al1);
            if(al0.size()>al1.size())
            {
                x=al0.size()-al1.size()-1;
                for(int i=0;i<x;i++)
                    sum+=al0.get(i);
            }
            else
            {
                x=al1.size()-al0.size()-1;
                for(int i=0;i<x;i++)
                    sum+=al1.get(i);
            }
            out.println(sum);
        }
    }
    
}
  class InputReader 
{
    private InputStream stream;
    private byte[] buf = new byte[8192];
    private int curChar, snumChars;
    private SpaceCharFilter filter;
 
    public InputReader(InputStream stream) 
    {
        this.stream = stream;
    }
 
    public int snext() 
    {
        if(snumChars==-1)
            throw new InputMismatchException();
        if(curChar>=snumChars)
        {
            curChar=0;
            try 
            {
                snumChars = stream.read(buf);                
            } 
            catch(IOException e) 
            {
                throw new InputMismatchException();
            }
            if(snumChars<=0)
                return -1;
        }
        return buf[curChar++];
    }
 
    public int nextInt()
    {
        int c = snext();
        while(isSpaceChar(c))
            c=snext();
        int sgn=1;
        if(c=='-')
        {
            sgn = -1;
            c = snext();
        }
        int res=0;
        do
        {
            if(c<'0' || c>'9')
                throw new InputMismatchException();
            res*=10;
            res+=c-'0';
            c=snext();
            }while(!isSpaceChar(c));
        return res * sgn;
    }
 
    public long nextLong()
    {
        int c = snext();
        while(isSpaceChar(c))
            c=snext();
        int sgn=1;
        if(c=='-')
        {
            sgn=-1;
            c=snext();
        }
        long res=0;
        do{
            if (c<'0' || c>'9')
                throw new InputMismatchException();
            res*=10;
            res+=c-'0';
            c=snext();
        }while (!isSpaceChar(c));
        return res * sgn;
    }
 
    public int[] nextIntArray(int n)
    {
        int a[]=new int[n];
        for(int i=0; i<n; i++)
            a[i]=nextInt();
        return a;
    }
 
    public String nextString()
    {
        int c=snext();
        while(isSpaceChar(c))
            c=snext();
        StringBuilder res=new StringBuilder();
        do{
            res.appendCodePoint(c);
            c = snext();
        }while (!isSpaceChar(c));
        return res.toString();
    }
 
    public boolean isSpaceChar(int c)
    {
        if(filter != null)
            return filter.isSpaceChar(c);
        return c==' ' || c=='\n' || c=='\r' || c=='\t' || c==-1;
    }
 
    public interface SpaceCharFilter
    {
        public boolean isSpaceChar(int ch);
    }
}