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
n=int(input())
a=[]
b=[]
for k in input().split(" "):
    if int(k)%2==0:
        a.append(int(k))
    else:
        b.append(int(k))
        
u=len(a)
v=len(b)
a.sort()
b.sort()
        
        
ans=[]        
if u>v:
    
    if u-v<2:
        ans.append(0)
    elif u-v==2:
        ans.append(a[0])
    else:
        q=0
        for i in range(0,len(a)-1-len(b)):
            q=q+a[i]
        ans.append(q)    
    if v!=0:    
        if u-v<1:
            ans.append(0)
        elif u-v==1:
            ans.append(a[0])
        else:
            q=0
            for i in range(0,len(a)-len(b)):
                q=q+a[i]
            ans.append(q)     
        
elif u==v:
    ans.append(0)
    
else:
    if v-u<2:
        ans.append(0)
    elif v-u==2:
        ans.append(b[0])
    else:
        q=0
        for i in range(0,len(b)-1-len(a)):
            q=q+b[i]
        ans.append(q)    
    if u!=0:    
        if v-u<1:
            ans.append(0)
        elif v-u==1:
            ans.append(b[0])
        else:
            q=0
            for i in range(0,len(b)-len(a)):
                q=q+b[i]
            ans.append(q)        
print(min(ans))            
    
        
    