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 \le n \le 2000$) — the number of elements of $a$.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 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

Difficulty: introductory

Starter code:

Solutions:
n = int(input())
a = list(map(int, input().split()))
odd = []
even = []
for i in a:
    if i%2:
        odd.append(i)
    else:
        even.append(i)
odd.sort()
even.sort()
if abs(len(odd) - len(even)) <= 1:
    print(0)
else:
    if len(odd) > len(even):
        print(sum(odd[:len(odd)-len(even)-1]))
    else:
        print(sum(even[:len(even) - len(odd)-1]))


n=int(input())
arr=list(map(int,input().split()))
arr1=[]
arr2=[]
for i in range(n):
    if(arr[i]%2==0):
        arr1.append(arr[i])
    else:
        arr2.append(arr[i])
arr1.sort(reverse=True)
arr2.sort(reverse=True)
if(len(arr1)==len(arr2)):
    print(0)
else:
    if(len(arr1)>len(arr2)):
        l=len(arr2)
        print(sum(arr1)-sum(arr1[:l+1]))
    else:
        l=len(arr1)
        print(sum(arr2)-sum(arr2[:l+1]))



n = int(input())
l = list(map(int,input().split()))
par = []
npar = []
for i in l:
	if i % 2 == 0:
		par.append(i)
	else:
		npar.append(i)
if abs(len(par) - len(npar)) <= 1:
	print(0)
else:
	if len(par) - len(npar) > 1:
		par = sorted(par)
		npar = sorted(npar)
		wyn = 0
		for i in range(len(par) - len(npar) - 1):
			wyn = wyn + par[i]
		print(wyn)
	if len(npar) - len(par) > 1:
		par = sorted(par)
		npar = sorted(npar)
		wyn = 0
		for i in range(len(npar) - len(par) - 1):
			wyn = wyn + npar[i]
		print(wyn)


N = int(input())
A = [int(a) for a in input().split()]

E = []
O = []

for a in A:
    if a % 2:
        O.append(a)
    else:
        E.append(a)

E = sorted(E)
O = sorted(O)

e = len(E)
o = len(O)

if e == o:
    print(0)
elif e < o:
    print(sum(O[:o-e-1]))
else:
    print(sum(E[:e-o-1]))


n = int(input())
A = list(map(int, input().split()))

chet = []
nechet = []

for i in A:
    if i % 2 == 0:
        chet.append(i)
    else:
        nechet.append(i)

if len(chet) == len(nechet) or abs(len(chet) - len(nechet)) == 1:
    print(0)
else:
    if len(chet) > len(nechet):
        print(sum(sorted(chet)[:len(chet) - len(nechet) - 1]))
    else:
        print(sum(sorted(nechet)[:len(nechet) - len(chet) - 1]))


n = int(input())
A = list(map(int, input().split()))
q1 = []
q2 = []
for i in A:
    if i % 2:
        q1.append(i)
    else:
        q2.append(i)
if abs(len(q1) - len(q2)) <= 1:
    print(0)
    return
if len(q1) < len(q2):
    q2.sort()
    print(sum(q2[:len(q2) - len(q1) - 1]))
else:
    q1.sort()
    print(sum(q1[:len(q1) - len(q2) - 1]))

n=int(input())
A=list(map(int,input().split()))

A0=[a for a in A if a%2==0]
A1=[a for a in A if a%2==1]

A0.sort()
A1.sort()

L0=len(A0)
L1=len(A1)

if abs(L0-L1)<=1:
    print(0)

elif L0>L1:
    x=L0-L1-1
    print(sum(A0[:x]))

elif L0<L1:
    x=L1-L0-1
    print(sum(A1[:x]))


'''input
5
1 5 7 8 2
'''
import sys
from collections import defaultdict as dd
from itertools import  permutations as pp
from itertools import combinations as cc
from collections import Counter as ccd
from random import randint as rd
from bisect import bisect_left as bl
import heapq
mod=10**9+7

def ri(flag=0):
	if flag==0:
		return [int(i) for i in sys.stdin.readline().split()]
	else:
		return int(sys.stdin.readline())

n=ri(1)
a=ri()
even=[]
odd=[]

for i in a:
	if i%2==0:
		even.append(i)
	else:
		odd.append(i)

even.sort(reverse=True)
odd.sort(reverse=True)

ans=0

i=0
j=0
f=0
while 1:
	try:
		if f==0:
			f=1
			ans+=even[i]
			i+=1
		else:
			f=0
			ans+=odd[j]
			j+=1
	except:
		break

ans1=0

i=0
j=0
f=1
while 1:
	try:
		if f==0:
			f=1
			ans1+=even[i]
			i+=1
		else:
			f=0
			ans1+=odd[j]
			j+=1
	except:
		break



print(sum(a)-max(ans,ans1))

#print(even,odd)


#Bhargey Mehta (Sophomore)
#DA-IICT, Gandhinagar
import sys, math, queue
sys.setrecursionlimit(1000000)
#sys.stdin = open("input.txt", "r")

n = int(input())
a = list(map(int, input().split()))
od = []
ev = []
for i in range(n):
    if a[i]%2 == 0: ev.append(a[i])
    else: od.append(a[i])
od.sort()
ev.sort()

if abs(len(od)-len(ev)) <= 1:
    print(0)
    return

ans = 0
if len(od) > len(ev):
    for i in range(len(od)-len(ev)-1):
        ans += od[i]
else:
    for i in range(len(ev)-len(od)-1):
        ans += ev[i]
print(ans)

''' CODED WITH LOVE BY SATYAM KUMAR '''

from sys import stdin, stdout
import cProfile, math
from collections import Counter,defaultdict
from bisect import bisect_left,bisect,bisect_right
import itertools
from copy import deepcopy
from fractions import Fraction
import sys, threading
import operator as op
from functools import reduce
sys.setrecursionlimit(10**6) # max depth of recursion
threading.stack_size(2**27)  # new thread will get stack of such size
fac_warmup = False
printHeap = str()
memory_constrained = False
P = 10**9+7
import sys

class merge_find:
    def __init__(self,n):
        self.parent = list(range(n))
        self.size = [1]*n
        self.num_sets = n
        self.lista = [[_] for _ in range(n)]
    def find(self,a):
        to_update = []
        while a != self.parent[a]:
            to_update.append(a)
            a = self.parent[a]
        for b in to_update:
            self.parent[b] = a
        return self.parent[a]
    def merge(self,a,b):
        a = self.find(a)
        b = self.find(b)
        if a==b:
            return
        if self.size[a]<self.size[b]:
            a,b = b,a
        self.num_sets -= 1
        self.parent[b] = a
        self.size[a] += self.size[b]
        self.lista[a] += self.lista[b]
    def set_size(self, a):
        return self.size[self.find(a)]
    def __len__(self):
        return self.num_sets

def display(string_to_print):
    stdout.write(str(string_to_print) + "\n")

def primeFactors(n): #n**0.5 complex 
    factors = dict()
    for i in range(2,math.ceil(math.sqrt(n))+1):  
        while n % i== 0: 
            if i in factors:
                factors[i]+=1
            else: factors[i]=1
            n = n // i 
    if n>2:
        factors[n]=1
    return (factors)

def fibonacci_modP(n,MOD):
    if n<2: return 1
    #print (n,MOD)
    return (cached_fn(fibonacci_modP, (n+1)//2, MOD)*cached_fn(fibonacci_modP, n//2, MOD) + cached_fn(fibonacci_modP, (n-1) // 2, MOD)*cached_fn(fibonacci_modP, (n-2) // 2, MOD)) % MOD

def factorial_modP_Wilson(n , p): 
    if (p <= n): 
        return 0
    res = (p - 1) 
    for i in range (n + 1, p): 
        res = (res * cached_fn(InverseEuler,i, p)) % p 
    return res 

def binary(n,digits = 20):
    b = bin(n)[2:]
    b = '0'*(20-len(b))+b
    return b

def isprime(n):
    """Returns True if n is prime."""
    if n < 4:
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False
    i = 5
    w = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += w
        w = 6 - w
    return True
factorial_modP = []
def warm_up_fac(MOD):
    nonlocal factorial_modP,fac_warmup
    if fac_warmup: return
    factorial_modP= [1 for _ in range(fac_warmup_size+1)]
    for i in range(2,fac_warmup_size):
        factorial_modP[i]= (factorial_modP[i-1]*i) % MOD
    fac_warmup = True

def InverseEuler(n,MOD):
    return pow(n,MOD-2,MOD)

def nCr(n, r, MOD):
    nonlocal fac_warmup,factorial_modP
    if not fac_warmup:
        warm_up_fac(MOD)
        fac_warmup = True
    return (factorial_modP[n]*((pow(factorial_modP[r], MOD-2, MOD) * pow(factorial_modP[n-r], MOD-2, MOD)) % MOD)) % MOD

def test_print(*args):
    if testingMode:
        print(args)

def display_list(list1, sep=" "):
    stdout.write(sep.join(map(str, list1)) + "\n")

def display_2D_list(li):
    for i in li:
        print(i)
def prefix_sum(li):
    sm = 0
    res = []
    for i in li:
        sm+=i
        res.append(sm)
    return res

def get_int():
    return int(stdin.readline().strip())

def get_tuple():
    return map(int, stdin.readline().split())

def get_list():
    return list(map(int, stdin.readline().split()))
import heapq,itertools
pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = '<removed-task>' 
def add_task(task, priority=0):
    'Add a new task or update the priority of an existing task'
    if task in entry_finder:
        remove_task(task)
    count = next(counter)
    entry = [priority, count, task]
    entry_finder[task] = entry
    heapq.heappush(pq, entry)

def remove_task(task):
    'Mark an existing task as REMOVED.  Raise KeyError if not found.'
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED

def pop_task():
    'Remove and return the lowest priority task. Raise KeyError if empty.'
    while pq:
        priority, count, task = heapq.heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue')
memory = dict()
def clear_cache():
    nonlocal memory
    memory = dict()
def cached_fn(fn, *args):
    nonlocal memory
    if args in memory:
        return memory[args]
    else:
        result = fn(*args)
        memory[args] = result
        return result

def ncr (n,r):
    return math.factorial(n)/(math.factorial(n-r)*math.factorial(r))
def binary_serach(i,li):
    #print("Search for ",i)
    fn = lambda x: li[x]-x//i
    x = -1
    b = len(li)
    while b>=1:
        #print(b,x)
        while b+x<len(li) and fn(b+x)>0: #Change this condition 2 to whatever you like
            x+=b
        b=b//2
    return x

# -------------------------------------------------------------- MAIN PROGRAM
TestCases = False
testingMode = False
fac_warmup_size = 10**5+100
optimiseForReccursion = True #Can not be used clubbed with TestCases # WHen using recursive functions, use Python 3
from math import factorial


def main():
    n = get_int()
    li = get_list()
    even = [x for x in li if x%2!=0]
    odd = [x for x in li if x%2==0]
    if abs(len(even)-len(odd))<2:
        print(0)
        return
    elif len(odd)>len(even):
        odd,even = even,odd
    even.sort()
    print(sum(even[:len(even)-len(odd)-1]))
    
# --------------------------------------------------------------------- END=


if TestCases: 
    for _ in range(get_int()): 
        cProfile.run('main()') if testingMode else main() 
else: (cProfile.run('main()') if testingMode else main()) if not optimiseForReccursion else threading.Thread(target=main).start()

import math
n=int(input())
arr=list(map(int,input().split()))
even=[]
odd=[]
for i in range(n):
	if arr[i]%2==0:
		even.append(arr[i])
	else:
		odd.append(arr[i])
if abs(len(even)-len(odd))<=1:
	print(0)
	return
if len(even)>len(odd):
	even.sort(reverse=True)
	ans=0
	for i in range(len(odd)+1,len(even)):
		ans+=even[i]
	print(ans)
	return
odd.sort(reverse=True)
ss=0
for i in range(len(even)+1,len(odd)):
	ss+=odd[i]
print(ss)

n = int(input())
l = list(map(int,input().split()))

odd = []
even = []
for i in l:
    if i%2:
        odd.append(i)
    else:
        even.append(i)

odd.sort()
even.sort()

lo = len(odd)
le = len(even)

if lo == le or lo == le+1 or lo == le-1:
    print(0)
else:

    if le > lo:
        diff = le - lo - 1
        ans = sum(even[:diff])
    else:
        diff = lo - le - 1
        ans = sum(odd[:diff])

    print(ans)


from bisect import bisect_right as br
from bisect import bisect_left as bl
from collections import *
from itertools import *
import functools
import sys
import math
import random
MAX = sys.maxsize
MAXN = 10**5+10
MOD = 10**9+7
def isprime(n):
    n = abs(int(n))
    if n < 2:
        return False
    if n == 2: 
        return True    
    if not n & 1: 
        return False
    for x in range(3, int(n**0.5) + 1, 2):
        if n % x == 0:
            return False
    return True

def mhd(a,b,x,y):
    return abs(a-x)+abs(b-y)

def numIN(x = " "):
    return(map(int,sys.stdin.readline().strip().split(x)))

def charIN():
    return(sys.stdin.readline().strip().split())

def dis(x,y):
    a = y[0]-x[0]
    b = x[1]-y[1]
    return (a*a+b*b)**0.5




n = int(input())
l = list(numIN())
e = []
o = []
for i in l:
    if i%2:
        o.append(i)
    else:
        e.append(i)
if len(e)==len(o):
    print(0)
else:
    e.sort(reverse=True)
    o.sort(reverse=True)
    mn = min(len(e),len(o))
    x = e[mn:]
    y = o[mn:]
    if x:
        print(sum(x)-x[0])
    else:
        print(sum(y)-y[0])

import sys

input = sys.stdin.readline

n = int(input())

evens = []
odds = []

for i in map(int, input().split()):
    if i % 2 == 0:
        evens.append(i)
    else:
        odds.append(i)
    
evens.sort(reverse = True)
odds.sort(reverse = True)

if len(evens) > len(odds):
    print(sum(evens[len(odds)+1:]))
elif len(odds) > len(evens):
    print(sum(odds[len(evens)+1:]))
else:
    print(0)

import heapq

n = int(input())
arr = list(map(int, input().split()))
ch = []
nc = []

for i in arr:
    if i % 2 == 0:
       ch.append(i)
    else:
        nc.append(i)
if len(ch) > len(nc):
    ans = sum(sorted(ch)[:len(ch) - len(nc) - 1])
elif len(ch) < len(nc):
    ans = sum(sorted(nc)[:len(nc) - len(ch) - 1])
else:
    ans = 0
print(ans)

n = int(input())
l = list(map(int, input().split()))
a = list()
b = list()
for i in l:
    if i % 2:
        a.append(i)
    else:
        b.append(i)
a.sort()
b.sort()
a.reverse()
b.reverse()
k = min(len(a), len(b))
if abs(len(a) - len(b)) < 2:
    print(0)
else:
    s = 0
    if len(a) < len(b):
        for i in range(k + 1, len(b)):
            s += b[i]
    else:
        for i in range(k + 1, len(a)):
            s += a[i]
    print(s)
        


GI = lambda: int(input()); GIS = lambda: list(map(int, input().split())); LGIS = lambda: list(GIS())

def main():
    GI()
    xs = GIS()
    ps = [[], []]
    for x in xs:
        ps[x % 2].append(x)
    ps.sort(key=len)
    lendiff = len(ps[1]) - len(ps[0])
    if lendiff > 1:
        large = ps[1]
        large.sort()
        print(sum(large[:lendiff-1]))
    else:
        print(0)

main()


# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
even = list([x for x in A if x % 2 == 0])
odd = list([x for x in A if x % 2 != 0])
even = sorted(even)
odd = sorted(odd)

evenN = len(even)
oddN = len(odd)

ans = -1
if abs(evenN-oddN) <= 1:
    ans = 0
else:
    if evenN > oddN:
        ans = sum(even[:evenN-oddN-1])
    else:
        ans = sum(odd[:oddN-evenN-1])
print(ans)


n = int(input())
arr = list(map(int, input().split()))
even, odd = [], []

for i in arr:
  if i%2 == 0:
    even += [i]
  else:
    odd += [i]

even = sorted(even)
odd = sorted(odd)

if len(even) == len(odd):
  print(0)
  return

elif len(even) < len(odd):
  even, odd = odd, even

#print(even, odd)

even.pop()
while even and odd:
  even.pop()
  odd.pop()

#print(even, odd)
print(sum(even))


n = int(input())
ints = list(map(int, input().split()))

even = []
odd = []

for i in ints:
    if i % 2 == 1:
        odd.append(i)
    else:
        even.append(i)

even.sort()
odd.sort()

if len(even) < len(odd):
    diff = len(odd) - len(even) - 1
    if diff > 0:
        print(sum(odd[0:diff]))
    else:
        print(0)
else:
    diff = len(even) - len(odd) - 1
    if diff > 0:
        print(sum(even[0:diff]))
    else:
        print(0)

import sys
import math
import heapq
import bisect
from collections import defaultdict as dd

n = int(input())
l = [int(i) for i in input().split()]
o = []
e = []
for i in l:
    if i%2==0:
        e.append(i)
    else:
        o.append(i)
o.sort()
e.sort()
if len(e) > len(o):
    o, e = e, o #o
for i in range(len(e)):
    e.pop(-1)
    o.pop(-1)
if o:
    o.pop(-1)
print(sum(o))