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
[{"code": "n = int(input())\na = list(map(int, input().split()))\nodd = []\neven = []\nfor i in a:\n    if i%2:\n        odd.append(i)\n    else:\n        even.append(i)\nodd.sort()\neven.sort()\nif abs(len(odd) - len(even)) <= 1:\n    print(0)\nelse:\n    if len(odd) > len(even):\n        print(sum(odd[:len(odd)-len(even)-1]))\n    else:\n        print(sum(even[:len(even) - len(odd)-1]))\n", "passed": true, "time": 0.23, "memory": 14344.0, "status": "done"}, {"code": "n=int(input())\narr=list(map(int,input().split()))\narr1=[]\narr2=[]\nfor i in range(n):\n    if(arr[i]%2==0):\n        arr1.append(arr[i])\n    else:\n        arr2.append(arr[i])\narr1.sort(reverse=True)\narr2.sort(reverse=True)\nif(len(arr1)==len(arr2)):\n    print(0)\nelse:\n    if(len(arr1)>len(arr2)):\n        l=len(arr2)\n        print(sum(arr1)-sum(arr1[:l+1]))\n    else:\n        l=len(arr1)\n        print(sum(arr2)-sum(arr2[:l+1]))\n\n", "passed": true, "time": 0.15, "memory": 14180.0, "status": "done"}, {"code": "n = int(input())\nl = list(map(int,input().split()))\npar = []\nnpar = []\nfor i in l:\n\tif i % 2 == 0:\n\t\tpar.append(i)\n\telse:\n\t\tnpar.append(i)\nif abs(len(par) - len(npar)) <= 1:\n\tprint(0)\nelse:\n\tif len(par) - len(npar) > 1:\n\t\tpar = sorted(par)\n\t\tnpar = sorted(npar)\n\t\twyn = 0\n\t\tfor i in range(len(par) - len(npar) - 1):\n\t\t\twyn = wyn + par[i]\n\t\tprint(wyn)\n\tif len(npar) - len(par) > 1:\n\t\tpar = sorted(par)\n\t\tnpar = sorted(npar)\n\t\twyn = 0\n\t\tfor i in range(len(npar) - len(par) - 1):\n\t\t\twyn = wyn + npar[i]\n\t\tprint(wyn)\n", "passed": true, "time": 0.15, "memory": 14240.0, "status": "done"}, {"code": "N = int(input())\nA = [int(a) for a in input().split()]\n\nE = []\nO = []\n\nfor a in A:\n    if a % 2:\n        O.append(a)\n    else:\n        E.append(a)\n\nE = sorted(E)\nO = sorted(O)\n\ne = len(E)\no = len(O)\n\nif e == o:\n    print(0)\nelif e < o:\n    print(sum(O[:o-e-1]))\nelse:\n    print(sum(E[:e-o-1]))\n", "passed": true, "time": 0.14, "memory": 14340.0, "status": "done"}, {"code": "n = int(input())\nA = list(map(int, input().split()))\n\nchet = []\nnechet = []\n\nfor i in A:\n    if i % 2 == 0:\n        chet.append(i)\n    else:\n        nechet.append(i)\n\nif len(chet) == len(nechet) or abs(len(chet) - len(nechet)) == 1:\n    print(0)\nelse:\n    if len(chet) > len(nechet):\n        print(sum(sorted(chet)[:len(chet) - len(nechet) - 1]))\n    else:\n        print(sum(sorted(nechet)[:len(nechet) - len(chet) - 1]))\n", "passed": true, "time": 0.15, "memory": 14300.0, "status": "done"}, {"code": "n = int(input())\nA = list(map(int, input().split()))\nq1 = []\nq2 = []\nfor i in A:\n    if i % 2:\n        q1.append(i)\n    else:\n        q2.append(i)\nif abs(len(q1) - len(q2)) <= 1:\n    print(0)\n    return\nif len(q1) < len(q2):\n    q2.sort()\n    print(sum(q2[:len(q2) - len(q1) - 1]))\nelse:\n    q1.sort()\n    print(sum(q1[:len(q1) - len(q2) - 1]))", "passed": true, "time": 0.24, "memory": 14368.0, "status": "done"}, {"code": "n=int(input())\nA=list(map(int,input().split()))\n\nA0=[a for a in A if a%2==0]\nA1=[a for a in A if a%2==1]\n\nA0.sort()\nA1.sort()\n\nL0=len(A0)\nL1=len(A1)\n\nif abs(L0-L1)<=1:\n    print(0)\n\nelif L0>L1:\n    x=L0-L1-1\n    print(sum(A0[:x]))\n\nelif L0<L1:\n    x=L1-L0-1\n    print(sum(A1[:x]))\n", "passed": true, "time": 0.22, "memory": 14104.0, "status": "done"}, {"code": "'''input\n5\n1 5 7 8 2\n'''\nimport sys\nfrom collections import defaultdict as dd\nfrom itertools import  permutations as pp\nfrom itertools import combinations as cc\nfrom collections import Counter as ccd\nfrom random import randint as rd\nfrom bisect import bisect_left as bl\nimport heapq\nmod=10**9+7\n\ndef ri(flag=0):\n\tif flag==0:\n\t\treturn [int(i) for i in sys.stdin.readline().split()]\n\telse:\n\t\treturn int(sys.stdin.readline())\n\nn=ri(1)\na=ri()\neven=[]\nodd=[]\n\nfor i in a:\n\tif i%2==0:\n\t\teven.append(i)\n\telse:\n\t\todd.append(i)\n\neven.sort(reverse=True)\nodd.sort(reverse=True)\n\nans=0\n\ni=0\nj=0\nf=0\nwhile 1:\n\ttry:\n\t\tif f==0:\n\t\t\tf=1\n\t\t\tans+=even[i]\n\t\t\ti+=1\n\t\telse:\n\t\t\tf=0\n\t\t\tans+=odd[j]\n\t\t\tj+=1\n\texcept:\n\t\tbreak\n\nans1=0\n\ni=0\nj=0\nf=1\nwhile 1:\n\ttry:\n\t\tif f==0:\n\t\t\tf=1\n\t\t\tans1+=even[i]\n\t\t\ti+=1\n\t\telse:\n\t\t\tf=0\n\t\t\tans1+=odd[j]\n\t\t\tj+=1\n\texcept:\n\t\tbreak\n\n\n\nprint(sum(a)-max(ans,ans1))\n\n#print(even,odd)\n", "passed": true, "time": 0.15, "memory": 14180.0, "status": "done"}, {"code": "#Bhargey Mehta (Sophomore)\n#DA-IICT, Gandhinagar\nimport sys, math, queue\nsys.setrecursionlimit(1000000)\n#sys.stdin = open(\"input.txt\", \"r\")\n\nn = int(input())\na = list(map(int, input().split()))\nod = []\nev = []\nfor i in range(n):\n    if a[i]%2 == 0: ev.append(a[i])\n    else: od.append(a[i])\nod.sort()\nev.sort()\n\nif abs(len(od)-len(ev)) <= 1:\n    print(0)\n    return\n\nans = 0\nif len(od) > len(ev):\n    for i in range(len(od)-len(ev)-1):\n        ans += od[i]\nelse:\n    for i in range(len(ev)-len(od)-1):\n        ans += ev[i]\nprint(ans)", "passed": true, "time": 0.14, "memory": 14400.0, "status": "done"}, {"code": "''' CODED WITH LOVE BY SATYAM KUMAR '''\n\nfrom sys import stdin, stdout\nimport cProfile, math\nfrom collections import Counter,defaultdict\nfrom bisect import bisect_left,bisect,bisect_right\nimport itertools\nfrom copy import deepcopy\nfrom fractions import Fraction\nimport sys, threading\nimport operator as op\nfrom functools import reduce\nsys.setrecursionlimit(10**6) # max depth of recursion\nthreading.stack_size(2**27)  # new thread will get stack of such size\nfac_warmup = False\nprintHeap = str()\nmemory_constrained = False\nP = 10**9+7\nimport sys\n\nclass merge_find:\n    def __init__(self,n):\n        self.parent = list(range(n))\n        self.size = [1]*n\n        self.num_sets = n\n        self.lista = [[_] for _ in range(n)]\n    def find(self,a):\n        to_update = []\n        while a != self.parent[a]:\n            to_update.append(a)\n            a = self.parent[a]\n        for b in to_update:\n            self.parent[b] = a\n        return self.parent[a]\n    def merge(self,a,b):\n        a = self.find(a)\n        b = self.find(b)\n        if a==b:\n            return\n        if self.size[a]<self.size[b]:\n            a,b = b,a\n        self.num_sets -= 1\n        self.parent[b] = a\n        self.size[a] += self.size[b]\n        self.lista[a] += self.lista[b]\n    def set_size(self, a):\n        return self.size[self.find(a)]\n    def __len__(self):\n        return self.num_sets\n\ndef display(string_to_print):\n    stdout.write(str(string_to_print) + \"\\n\")\n\ndef primeFactors(n): #n**0.5 complex \n    factors = dict()\n    for i in range(2,math.ceil(math.sqrt(n))+1):  \n        while n % i== 0: \n            if i in factors:\n                factors[i]+=1\n            else: factors[i]=1\n            n = n // i \n    if n>2:\n        factors[n]=1\n    return (factors)\n\ndef fibonacci_modP(n,MOD):\n    if n<2: return 1\n    #print (n,MOD)\n    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\n\ndef factorial_modP_Wilson(n , p): \n    if (p <= n): \n        return 0\n    res = (p - 1) \n    for i in range (n + 1, p): \n        res = (res * cached_fn(InverseEuler,i, p)) % p \n    return res \n\ndef binary(n,digits = 20):\n    b = bin(n)[2:]\n    b = '0'*(20-len(b))+b\n    return b\n\ndef isprime(n):\n    \"\"\"Returns True if n is prime.\"\"\"\n    if n < 4:\n        return True\n    if n % 2 == 0:\n        return False\n    if n % 3 == 0:\n        return False\n    i = 5\n    w = 2\n    while i * i <= n:\n        if n % i == 0:\n            return False\n        i += w\n        w = 6 - w\n    return True\nfactorial_modP = []\ndef warm_up_fac(MOD):\n    nonlocal factorial_modP,fac_warmup\n    if fac_warmup: return\n    factorial_modP= [1 for _ in range(fac_warmup_size+1)]\n    for i in range(2,fac_warmup_size):\n        factorial_modP[i]= (factorial_modP[i-1]*i) % MOD\n    fac_warmup = True\n\ndef InverseEuler(n,MOD):\n    return pow(n,MOD-2,MOD)\n\ndef nCr(n, r, MOD):\n    nonlocal fac_warmup,factorial_modP\n    if not fac_warmup:\n        warm_up_fac(MOD)\n        fac_warmup = True\n    return (factorial_modP[n]*((pow(factorial_modP[r], MOD-2, MOD) * pow(factorial_modP[n-r], MOD-2, MOD)) % MOD)) % MOD\n\ndef test_print(*args):\n    if testingMode:\n        print(args)\n\ndef display_list(list1, sep=\" \"):\n    stdout.write(sep.join(map(str, list1)) + \"\\n\")\n\ndef display_2D_list(li):\n    for i in li:\n        print(i)\ndef prefix_sum(li):\n    sm = 0\n    res = []\n    for i in li:\n        sm+=i\n        res.append(sm)\n    return res\n\ndef get_int():\n    return int(stdin.readline().strip())\n\ndef get_tuple():\n    return map(int, stdin.readline().split())\n\ndef get_list():\n    return list(map(int, stdin.readline().split()))\nimport heapq,itertools\npq = []                         # list of entries arranged in a heap\nentry_finder = {}               # mapping of tasks to entries\nREMOVED = '<removed-task>' \ndef add_task(task, priority=0):\n    'Add a new task or update the priority of an existing task'\n    if task in entry_finder:\n        remove_task(task)\n    count = next(counter)\n    entry = [priority, count, task]\n    entry_finder[task] = entry\n    heapq.heappush(pq, entry)\n\ndef remove_task(task):\n    'Mark an existing task as REMOVED.  Raise KeyError if not found.'\n    entry = entry_finder.pop(task)\n    entry[-1] = REMOVED\n\ndef pop_task():\n    'Remove and return the lowest priority task. Raise KeyError if empty.'\n    while pq:\n        priority, count, task = heapq.heappop(pq)\n        if task is not REMOVED:\n            del entry_finder[task]\n            return task\n    raise KeyError('pop from an empty priority queue')\nmemory = dict()\ndef clear_cache():\n    nonlocal memory\n    memory = dict()\ndef cached_fn(fn, *args):\n    nonlocal memory\n    if args in memory:\n        return memory[args]\n    else:\n        result = fn(*args)\n        memory[args] = result\n        return result\n\ndef ncr (n,r):\n    return math.factorial(n)/(math.factorial(n-r)*math.factorial(r))\ndef binary_serach(i,li):\n    #print(\"Search for \",i)\n    fn = lambda x: li[x]-x//i\n    x = -1\n    b = len(li)\n    while b>=1:\n        #print(b,x)\n        while b+x<len(li) and fn(b+x)>0: #Change this condition 2 to whatever you like\n            x+=b\n        b=b//2\n    return x\n\n# -------------------------------------------------------------- MAIN PROGRAM\nTestCases = False\ntestingMode = False\nfac_warmup_size = 10**5+100\noptimiseForReccursion = True #Can not be used clubbed with TestCases # WHen using recursive functions, use Python 3\nfrom math import factorial\n\n\ndef main():\n    n = get_int()\n    li = get_list()\n    even = [x for x in li if x%2!=0]\n    odd = [x for x in li if x%2==0]\n    if abs(len(even)-len(odd))<2:\n        print(0)\n        return\n    elif len(odd)>len(even):\n        odd,even = even,odd\n    even.sort()\n    print(sum(even[:len(even)-len(odd)-1]))\n    \n# --------------------------------------------------------------------- END=\n\n\nif TestCases: \n    for _ in range(get_int()): \n        cProfile.run('main()') if testingMode else main() \nelse: (cProfile.run('main()') if testingMode else main()) if not optimiseForReccursion else threading.Thread(target=main).start()", "passed": true, "time": 0.16, "memory": 16092.0, "status": "done"}, {"code": "import math\nn=int(input())\narr=list(map(int,input().split()))\neven=[]\nodd=[]\nfor i in range(n):\n\tif arr[i]%2==0:\n\t\teven.append(arr[i])\n\telse:\n\t\todd.append(arr[i])\nif abs(len(even)-len(odd))<=1:\n\tprint(0)\n\treturn\nif len(even)>len(odd):\n\teven.sort(reverse=True)\n\tans=0\n\tfor i in range(len(odd)+1,len(even)):\n\t\tans+=even[i]\n\tprint(ans)\n\treturn\nodd.sort(reverse=True)\nss=0\nfor i in range(len(even)+1,len(odd)):\n\tss+=odd[i]\nprint(ss)", "passed": true, "time": 0.14, "memory": 14124.0, "status": "done"}, {"code": "n = int(input())\nl = list(map(int,input().split()))\n\nodd = []\neven = []\nfor i in l:\n    if i%2:\n        odd.append(i)\n    else:\n        even.append(i)\n\nodd.sort()\neven.sort()\n\nlo = len(odd)\nle = len(even)\n\nif lo == le or lo == le+1 or lo == le-1:\n    print(0)\nelse:\n\n    if le > lo:\n        diff = le - lo - 1\n        ans = sum(even[:diff])\n    else:\n        diff = lo - le - 1\n        ans = sum(odd[:diff])\n\n    print(ans)\n", "passed": true, "time": 0.14, "memory": 14196.0, "status": "done"}, {"code": "import sys\n\ninput = sys.stdin.readline\n\nn = int(input())\n\nevens = []\nodds = []\n\nfor i in map(int, input().split()):\n    if i % 2 == 0:\n        evens.append(i)\n    else:\n        odds.append(i)\n    \nevens.sort(reverse = True)\nodds.sort(reverse = True)\n\nif len(evens) > len(odds):\n    print(sum(evens[len(odds)+1:]))\nelif len(odds) > len(evens):\n    print(sum(odds[len(evens)+1:]))\nelse:\n    print(0)", "passed": true, "time": 0.14, "memory": 14272.0, "status": "done"}, {"code": "import heapq\n\nn = int(input())\narr = list(map(int, input().split()))\nch = []\nnc = []\n\nfor i in arr:\n    if i % 2 == 0:\n       ch.append(i)\n    else:\n        nc.append(i)\nif len(ch) > len(nc):\n    ans = sum(sorted(ch)[:len(ch) - len(nc) - 1])\nelif len(ch) < len(nc):\n    ans = sum(sorted(nc)[:len(nc) - len(ch) - 1])\nelse:\n    ans = 0\nprint(ans)", "passed": true, "time": 0.14, "memory": 14128.0, "status": "done"}, {"code": "n = int(input())\nl = list(map(int, input().split()))\na = list()\nb = list()\nfor i in l:\n    if i % 2:\n        a.append(i)\n    else:\n        b.append(i)\na.sort()\nb.sort()\na.reverse()\nb.reverse()\nk = min(len(a), len(b))\nif abs(len(a) - len(b)) < 2:\n    print(0)\nelse:\n    s = 0\n    if len(a) < len(b):\n        for i in range(k + 1, len(b)):\n            s += b[i]\n    else:\n        for i in range(k + 1, len(a)):\n            s += a[i]\n    print(s)\n        \n", "passed": true, "time": 0.14, "memory": 14076.0, "status": "done"}, {"code": "GI = lambda: int(input()); GIS = lambda: list(map(int, input().split())); LGIS = lambda: list(GIS())\n\ndef main():\n    GI()\n    xs = GIS()\n    ps = [[], []]\n    for x in xs:\n        ps[x % 2].append(x)\n    ps.sort(key=len)\n    lendiff = len(ps[1]) - len(ps[0])\n    if lendiff > 1:\n        large = ps[1]\n        large.sort()\n        print(sum(large[:lendiff-1]))\n    else:\n        print(0)\n\nmain()\n", "passed": true, "time": 0.14, "memory": 14256.0, "status": "done"}, {"code": "# python template for atcoder1\nimport sys\nsys.setrecursionlimit(10**9)\ninput = sys.stdin.readline\n\nN = int(input())\nA = list(map(int, input().split()))\neven = list([x for x in A if x % 2 == 0])\nodd = list([x for x in A if x % 2 != 0])\neven = sorted(even)\nodd = sorted(odd)\n\nevenN = len(even)\noddN = len(odd)\n\nans = -1\nif abs(evenN-oddN) <= 1:\n    ans = 0\nelse:\n    if evenN > oddN:\n        ans = sum(even[:evenN-oddN-1])\n    else:\n        ans = sum(odd[:oddN-evenN-1])\nprint(ans)\n", "passed": true, "time": 0.14, "memory": 14252.0, "status": "done"}, {"code": "n = int(input())\narr = list(map(int, input().split()))\neven, odd = [], []\n\nfor i in arr:\n  if i%2 == 0:\n    even += [i]\n  else:\n    odd += [i]\n\neven = sorted(even)\nodd = sorted(odd)\n\nif len(even) == len(odd):\n  print(0)\n  return\n\nelif len(even) < len(odd):\n  even, odd = odd, even\n\n#print(even, odd)\n\neven.pop()\nwhile even and odd:\n  even.pop()\n  odd.pop()\n\n#print(even, odd)\nprint(sum(even))\n", "passed": true, "time": 0.14, "memory": 14152.0, "status": "done"}, {"code": "n = int(input())\nints = list(map(int, input().split()))\n\neven = []\nodd = []\n\nfor i in ints:\n    if i % 2 == 1:\n        odd.append(i)\n    else:\n        even.append(i)\n\neven.sort()\nodd.sort()\n\nif len(even) < len(odd):\n    diff = len(odd) - len(even) - 1\n    if diff > 0:\n        print(sum(odd[0:diff]))\n    else:\n        print(0)\nelse:\n    diff = len(even) - len(odd) - 1\n    if diff > 0:\n        print(sum(even[0:diff]))\n    else:\n        print(0)", "passed": true, "time": 0.14, "memory": 14116.0, "status": "done"}, {"code": "import sys\nimport math\nimport heapq\nimport bisect\nfrom collections import defaultdict as dd\n\nn = int(input())\nl = [int(i) for i in input().split()]\no = []\ne = []\nfor i in l:\n    if i%2==0:\n        e.append(i)\n    else:\n        o.append(i)\no.sort()\ne.sort()\nif len(e) > len(o):\n    o, e = e, o #o\nfor i in range(len(e)):\n    e.pop(-1)\n    o.pop(-1)\nif o:\n    o.pop(-1)\nprint(sum(o))", "passed": true, "time": 0.14, "memory": 14244.0, "status": "done"}]