Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

There are $N$ workers; each worker is of one of the following three types:
A *translator* translates some text from Chef's language to another langague.
An *author* writes some text in Chef's language.
An *author-translator* can both write a text in Chef's language and translate it to another language.

Chef wants to have some text written and translated into some language (different from Chef's language). Chef can't do either of those tasks, but he can hire workers. For each $i$ ($1 ≤ i ≤ N$), if he hires the $i$-th worker, he must pay that worker $c_{i}$ coins.

Help Chef find the minimum total number of coins he needs to pay to have a text written and translated. It is guaranteed that it is possible to write and translate a text.

------  Input ------
The first line of the input contains a single integer $N$ denoting the number of workers.
The second line contins $N$ space-separated integers $c_{1}, c_{2}, ..., c_{N}$ denoting the numbers of coins Chef has to pay each hired worker.
The third line contains $N$ space-separated integers $t_{1}, t_{2}, ..., t_{N}$ denoting the types of workers. For each valid $i$, the $i$-th worker is a translator if $t_{i} = 1$, an author if $t_{i} = 2$ or an author-translator if $t_{i} = 3$.

------  Output ------
Print a single line containing one integer — the minimum number of coins Chef has to pay.

------  Constraints ------
$1 ≤ N ≤ 1,000$
$1 ≤ c_{i} ≤ 100,000$ for each valid $i$
$1 ≤ t_{i} ≤ 3$ for each valid $i$

------  Subtasks ------
Subtask #1 (15 points): all workers are author-translators

Subtask #2 (85 points): original constraints

----- Sample Input 1 ------ 
5
1 3 4 6 8
1 2 1 2 3
----- Sample Output 1 ------ 
4
----- explanation 1 ------ 
Chef can hire 2 workers: worker 1, who is a translator, and worker 2, who is an author. In total, he pays them $1 + 3 = 4$ coins.

Source: codechef | Difficulty: EASY
Tags: Constructive algorithms

Ad-hoc


Solutions:
n = int(input())
c = list(map(int, input().split()))
t = list(map(int, input().split()))
p = []
q = []
r = []
for i in range(n):
	if t[i] == 1:
		p.append(c[i])
	elif t[i] == 2:
		q.append(c[i])
	else:
		r.append(c[i])
if len(p) == 0:
	x = 1000000
else:
	x = min(p)
if len(q) == 0:
	y = 1000000
else:
	y = min(q)
if len(r) == 0:
	z = 1000000
else:
	z = min(r)
if x + y < z:
	print(x + y)
else:
	print(z)


n = int(input())
arr = list(map(int, input().split()))
arr1 = list(map(int, input().split()))
l = []
for i in range(n):
	if arr1[i] == 3:
		l.append(arr[i])
for i in range(n):
	if arr1[i] == 1:
		for j in range(n):
			if arr1[j] == 2:
				l.append(arr[i] + arr[j])
print(min(l))


N = int(input())
c = list(map(int, input().split()))
t = list(map(int, input().split()))
costs = []
for i in range(0, len(t)):
	if t[i] == 3:
		costs.append(c[i])
	if t[i] == 2:
		for j in range(0, len(t)):
			if t[j] == 1:
				costs.append(c[i] + c[j])
print(min(costs))


n = int(input())
c = list(map(int, input().split()))
w = list(map(int, input().split()))
one = 100000
two = 100000
three = 100000
for i in range(n):
	if w[i] == 1:
		one = min(one, c[i])
	elif w[i] == 2:
		two = min(two, c[i])
	else:
		three = min(three, c[i])
print(three if one + two > three else one + two)


n = int(input())
coins = list(map(int, input().split()))
types = list(map(int, input().split()))
min_1 = 100001
min_2 = 100001
min_3 = 100001
for i in range(n):
	if types[i] == 1:
		if coins[i] < min_1:
			min_1 = coins[i]
	elif types[i] == 2:
		if coins[i] < min_2:
			min_2 = coins[i]
	elif coins[i] < min_3:
		min_3 = coins[i]
print(min(min_1 + min_2, min_3))


n = int(input())
c = list(map(int, input().split()))
w = list(map(int, input().split()))
min = 0
for i in range(n):
	if min == 0:
		if w[i] == 3:
			min = c[i]
	elif w[i] == 3 and c[i] < min:
		min = c[i]
if min == 0:
	for i in range(n):
		if w[i] == 1:
			q = c[i]
			for j in range(n):
				if w[j] == 2:
					min = c[j] + q
					break
for j in range(n):
	if w[j] == 1:
		t = c[j]
		for k in range(n):
			if w[k] == 2:
				if t + c[k] < min:
					min = t + c[k]
print(min)


n = int(input())
c = list(map(int, input().split()))
t = list(map(int, input().split()))
a = []
b = []
d = []
for i in range(0, len(t)):
	if t[i] == 1:
		a.append(c[i])
	elif t[i] == 2:
		b.append(c[i])
	else:
		d.append(c[i])
if len(a) == 0:
	x = 2342342
else:
	x = min(a)
if len(b) == 0:
	y = 2342342
else:
	y = min(b)
if len(d) == 0:
	z = 2342342
else:
	z = min(d)
if x + y >= z:
	print(z)
else:
	print(x + y)


n = int(input())
c = list(map(int, input().split()))
w = list(map(int, input().split()))
l = []
for i in range(n):
	l.append([w[i], c[i]])
(a, t, b) = (0, 0, 0)
for i in l:
	c1 = i[1]
	w1 = i[0]
	if w1 == 1:
		if a != 0:
			if c1 < a:
				a = c1
		else:
			a = c1
	if w1 == 2:
		if t != 0:
			if c1 < t:
				t = c1
		else:
			t = c1
	if w1 == 3:
		if b != 0:
			if c1 < b:
				b = c1
		else:
			b = c1
if b == 0:
	print(a + t)
elif a + t < b and a != 0 and (t != 0):
	print(a + t)
else:
	print(b)


n = int(input())
c = list(map(int, input().split()))
t = list(map(int, input().split()))
co = 99999
i = 0
while i < n:
	e = t[i]
	if e != 3:
		for j in range(i + 1, n):
			if t[j] + e == 3:
				if c[i] + c[j] < co:
					co = c[i] + c[j]
	elif co > c[i]:
		co = c[i]
	i += 1
print(co)


q = int(input())
x = list(map(int, input().split()))
v = list(map(int, input().split()))
c = 0
a = 100000000000000000000000000000
s = 100000000000000000000000000000
b = 100000000000000000000000000000
for i in v:
	if i == 1:
		if x[c] < a:
			a = x[c]
	elif i == 2:
		if x[c] < s:
			s = x[c]
	elif x[c] < b:
		b = x[c]
	c = c + 1
z = a + s
if z > b:
	print(b)
else:
	print(z)


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
p = []
q = []
r = []
for i in range(n):
	if b[i] == 1:
		p.append(a[i])
for i in range(n):
	if b[i] == 2:
		q.append(a[i])
for i in range(n):
	if b[i] == 3:
		r.append(a[i])
if len(p) == 0:
	x = 100001
else:
	x = min(p)
if len(q) == 0:
	y = 100001
else:
	y = min(q)
if len(r) == 0:
	z = 100001
else:
	z = min(r)
if x + y <= z:
	print(x + y)
else:
	print(z)


totalWokers = int(input())
coins = list(map(int, input().split()))
workers = list(map(int, input().split()))
k = []
for i in range(totalWokers):
	if workers[i] == 3:
		k.append(coins[i])
for i in range(totalWokers):
	if workers[i] == 1:
		for j in range(totalWokers):
			if workers[j] == 2:
				k.append(coins[i] + coins[j])
print(min(k))


n = int(input())
c = list(map(int, input().split()))
t = list(map(int, input().split()))
found3 = 0
min3 = 0
found2 = 0
min2 = 0
found1 = 0
min1 = 0
for j in range(len(t)):
	if t[j] == 3:
		found3 = 1
		if min3 == 0:
			min3 = c[j]
		elif c[j] < min3:
			min3 = c[j]
	if t[j] == 1:
		found1 = 1
		if min1 == 0:
			min1 = c[j]
		elif c[j] < min1:
			min1 = c[j]
	if t[j] == 2:
		found2 = 1
		if min2 == 0:
			min2 = c[j]
		elif c[j] < min2:
			min2 = c[j]
if found1 == 1 and found2 == 1 and (found3 == 1):
	print(min(min1 + min2, min3))
elif found1 == 1 and found2 == 1 and (found3 == 0):
	print(min1 + min2)
else:
	print(min3)


n = int(input())
c = list(map(int, input().split()))
d = list(map(int, input().split()))
a = []
for i in range(n):
	if d[i] == 3:
		a.append(c[i])
for i in range(n):
	if d[i] == 1:
		for j in range(n):
			if d[j] == 2:
				a.append(c[i] + c[j])
print(min(a))


n = int(input())
c = list(map(int, input().split()))
t = list(map(int, input().split()))
k = []
for i in range(n):
	if t[i] == 3:
		k.append(c[i])
for i in range(n):
	if t[i] == 1:
		for j in range(n):
			if t[j] == 2:
				k.append(c[i] + c[j])
print(min(k))


n = int(input())
ct = list(zip(map(int, input().split()), map(int, input().split())))
t = min([c for (c, t) in ct if t == 1], default=100000)
a = min([c for (c, a) in ct if a == 2], default=100000)
at = min([c for (c, at) in ct if at == 3], default=100000)
print(min(t + a, at))


n = int(input())
l1 = list(map(int, input().split()))
l2 = list(map(int, input().split()))
l3 = []
for i in range(n):
	if l2[i] == 3:
		l3.append(l1[i])
for i in range(n):
	if l2[i] == 1:
		for j in range(n):
			if l2[j] == 2:
				l3.append(l1[i] + l1[j])
print(min(l3))


n = int(input())
coins = list(map(int, input().split(' ')))
types = list(map(int, input().split(' ')))
o = []
t = []
th = []
for i in range(len(coins)):
	if types[i] == 1:
		o.append(coins[i])
	elif types[i] == 2:
		t.append(coins[i])
	else:
		th.append(coins[i])
if len(th) == 0:
	print(min(o) + min(t))
elif len(t) == 0 or len(o) == 0:
	print(min(th))
elif min(o) + min(t) < min(th):
	print(min(o) + min(t))
else:
	print(min(th))


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = []
for i in range(n):
	if b[i] == 3:
		l.append(a[i])
for i in range(n):
	if b[i] == 1:
		for j in range(n):
			if b[j] == 2:
				l.append(a[i] + a[j])
print(min(l))


N = int(input())
p = list(map(int, input().split()))
w = list(map(int, input().split()))
minval = 100
val = []
for i in range(N):
	if w[i] == 3:
		val.append(p[i])
for i in range(N):
	if w[i] == 1:
		for j in range(N):
			if w[j] == 2:
				val.append(p[i] + p[j])
print(min(val))


n = int(input())
C = list(map(int, input().split()))
T = list(map(int, input().split()))
L = []
for i in range(n):
	if T[i] == 3:
		L.append(C[i])
for i in range(n):
	if T[i] == 1:
		for j in range(n):
			if T[j] == 2:
				L.append(C[i] + C[j])
print(min(L))


n = int(input())
l = list(map(int, input().split()))
l1 = list(map(int, input().split()))
(l2, l3, l4) = ([], [], [])
(r1, r2) = (10000, 10000)
for (x, y) in zip(l, l1):
	if y == 1:
		l2.append(x)
	elif y == 2:
		l3.append(x)
	else:
		l4.append(x)
if l2 != [] and l3 != []:
	r1 = min(l2) + min(l3)
if l4 != []:
	r2 = min(l4)
print(min(r1, r2))


t = int(input())
d = {1: [1000000], 2: [10000000], 3: [1000000000]}
c = list(map(int, input().split()))
n = list(map(int, input().split()))
for i in range(t):
	if n[i] == 1:
		d[1].append(c[i])
	elif n[i] == 2:
		d[2].append(c[i])
	else:
		d[3].append(c[i])
print(min(min(d[1]) + min(d[2]), min(d[3])))


t = int(input())
d = {1: [10000000000], 2: [1000000000000], 3: [100000000000000]}
c = list(map(int, input().split()))
n = list(map(int, input().split()))
for i in range(t):
	if n[i] == 1:
		d[1].append(c[i])
	elif n[i] == 2:
		d[2].append(c[i])
	else:
		d[3].append(c[i])
print(min(min(d[1]) + min(d[2]), min(d[3])))


n = int(input())
li = list(map(int, input().split()))
li2 = list(map(int, input().split()))
mo = max(li)
mt = max(li)
mth = max(li)
for i in range(n):
	if li2[i] == 1:
		mo = min(mo, li[i])
	elif li2[i] == 2:
		mt = min(mt, li[i])
	else:
		mth = min(mth, li[i])
print(min(mo + mt, mth))


n = int(input())
l1 = list(map(int, input().split()))
l2 = list(map(int, input().split()))
p1 = max(l1)
p2 = max(l1)
p3 = max(l1)
for i in range(n):
	if l2[i] == 1:
		p1 = min(p1, l1[i])
	elif l2[i] == 2:
		p2 = min(p2, l1[i])
	else:
		p3 = min(p3, l1[i])
print(min(p1 + p2, p3))


n = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
a1 = []
a2 = []
a3 = []
m = 99999
n = 99999
for (i, k) in zip(x, y):
	if k == 1:
		a1.append(i)
	elif k == 2:
		a2.append(i)
	else:
		a3.append(i)
if a1 != [] and a2 != []:
	m = min(a1) + min(a2)
if a3 != []:
	n = min(a3)
print(min(m, n))


n = int(input())
c = [int(x) for x in input().split()]
t = [int(x) for x in input().split()]
d = {1: 999999, 2: 999999, 3: 999999}
for i in range(n):
	if t[i] == 1:
		d[1] = min([c[i], d[1]])
	elif t[i] == 2:
		d[2] = min([c[i], d[2]])
	else:
		d[3] = min([c[i], d[3]])
print(min([d[1] + d[2], d[3]]))


n = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
(x, y, z) = (10000, 10000, 10000)
for j in range(n):
	if b[j] == 1:
		if a[j] < x:
			x = a[j]
	elif b[j] == 2:
		if a[j] < y:
			y = a[j]
	elif a[j] < z:
		z = a[j]
print(min(x + y, z))


import sys
n = int(input())
c = [int(x) for x in input().split()]
t = [int(x) for x in input().split()]
(min1, min2, min3) = (sys.maxsize, sys.maxsize, sys.maxsize)
for i in range(n):
	if t[i] == 1:
		if c[i] < min1:
			min1 = c[i]
	elif t[i] == 2:
		if c[i] < min2:
			min2 = c[i]
	elif t[i] == 3:
		if c[i] < min3:
			min3 = c[i]
if min1 + min2 < min3:
	print(min1 + min2)
else:
	print(min3)


n = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
d = {1: 999999, 2: 999999, 3: 999999}
for i in range(n):
	if b[i] == 1:
		d[1] = min([a[i], d[1]])
	elif b[i] == 2:
		d[2] = min([a[i], d[2]])
	else:
		d[3] = min([a[i], d[3]])
print(min([d[1] + d[2], d[3]]))


N = int(input())
c = list(map(int, input().split()))
t = list(map(int, input().split()))
a = max(c)
tr = max(c)
m = max(c)
for i in range(N):
	if t[i] == 1:
		if c[i] <= a:
			a = c[i]
	elif t[i] == 2:
		if c[i] <= tr:
			tr = c[i]
	elif c[i] <= m:
		m = c[i]
print(min(a + tr, m))


n = int(input())
c = list(map(int, input().split()))
t = list(map(int, input().split()))
auth = max(c)
trans = max(c)
mix = max(c)
for i in range(n):
	if t[i] == 1:
		if c[i] <= auth:
			auth = c[i]
	elif t[i] == 2:
		if c[i] <= trans:
			trans = c[i]
	elif c[i] <= mix:
		mix = c[i]
print(min(auth + trans, mix))


n = int(input())
money = list(map(int, input().split()))[:n]
ty = list(map(int, input().split()))[:n]
cost1 = 100000
cost2 = 100000
cost3 = 100000
for i in range(n):
	if ty[i] == 1:
		cost1 = min(cost1, money[i])
	elif ty[i] == 2:
		cost2 = min(cost2, money[i])
	else:
		cost3 = min(cost3, money[i])
cost = cost1 + cost2
print(cost if cost <= cost3 else cost3)


n = int(input())
l = list(map(int, input().split()))
t = list(map(int, input().split()))
d = {1: 0, 2: 0, 3: 0}
for i in range(n):
	if d[t[i]] == 0:
		d[t[i]] = l[i]
	elif d[t[i]] > l[i]:
		d[t[i]] = l[i]
if d[1] + d[2] > d[3] and d[3] != 0:
	print(d[3])
elif d[1] != 0 and d[2] != 0:
	print(d[1] + d[2])
else:
	print(d[3])


n = int(input())
c = list(map(int, input().split()))
w = list(map(int, input().split()))
(c1, c2, c3) = (1000000, 1000000, 1000000)
for i in range(n):
	if w[i] == 1:
		if c1 > c[i]:
			c1 = c[i]
	elif w[i] == 2:
		if c2 > c[i]:
			c2 = c[i]
	elif c3 > c[i]:
		c3 = c[i]
print(min(c1 + c2, c3))


n = int(input())
x = [int(i) for i in input().split(' ', n - 1)]
y = [int(i) for i in input().split(' ', n - 1)]
li = []
li1 = []
li2 = []
for i in range(n):
	if y[i] == 1:
		li.append(x[i])
	elif y[i] == 2:
		li1.append(x[i])
	else:
		li2.append(x[i])
b = []
for i in li:
	for j in li1:
		b.append(i + j)
for i in li2:
	b.append(i)
print(min(b))


minTranslator = 100000
minAuthor = 100000
minBoth = 100000
n = int(input())
cost = list(map(int, input().split(' ')))
work = list(map(int, input().split(' ')))
for i in range(n):
	if work[i] == 1:
		if cost[i] < minTranslator:
			minTranslator = cost[i]
	elif work[i] == 2:
		if cost[i] < minAuthor:
			minAuthor = cost[i]
	elif cost[i] < minBoth:
		minBoth = cost[i]
if minAuthor + minTranslator > minBoth:
	print(minBoth)
else:
	print(minTranslator + minAuthor)


n = int(input())
c = list(map(int, input().split()))
t = list(map(int, input().split()))
c1 = 100000
c2 = 100000
c3 = 100000
for i in range(len(t)):
	if t[i] == 1:
		if c[i] < c1:
			c1 = c[i]
	elif t[i] == 2:
		if c[i] < c2:
			c2 = c[i]
	elif c[i] < c3:
		c3 = c[i]
if c1 + c2 < c3:
	print(c1 + c2)
else:
	print(c3)


n = int(input())
coins = [int(x) for x in input().split()]
types = [int(x) for x in input().split()]
translators = []
authors = []
author_translators = []
for i in range(n):
	if types[i] == 1:
		translators.append(coins[i])
	elif types[i] == 2:
		authors.append(coins[i])
	else:
		author_translators.append(coins[i])
min_translator = min(translators) if len(translators) > 0 else float('inf')
min_author = min(authors) if len(authors) > 0 else float('inf')
min_author_translator = min(author_translators) if len(author_translators) > 0 else float('inf')
min_total = float('inf')
if min_translator != float('inf') and min_author != float('inf'):
	min_total = min_translator + min_author
min_total = min(min_total, min_author_translator)
print(min_total)


N = int(input())
C = list(map(int, input().split(' ', N)))
T = list(map(int, input().split(' ', N)))
author = []
translator = []
both = []
for i in range(N):
	if T[i] == 1:
		author.append(C[i])
	elif T[i] == 2:
		translator.append(C[i])
	elif T[i] == 3:
		both.append(C[i])
for j in author:
	for k in translator:
		both.append(j + k)
print(min(both))


a = int(input())
t = list(map(int, input().split()))
b = list(map(int, input().split()))
c = 10000
d = 10000
f = 10000
for j in range(len(b)):
	if b[j] == 1:
		if t[j] < c:
			c = t[j]
	elif b[j] == 2:
		if t[j] < d:
			d = t[j]
	elif t[j] < f:
		f = t[j]
print(min(c + d, f))


n = int(input())
c = list(map(int, input().split()))
t = list(map(int, input().split()))
m1 = m2 = m3 = 100000
for i in range(n):
	if t[i] == 1:
		if c[i] < m1:
			m1 = c[i]
	elif t[i] == 2:
		if c[i] < m2:
			m2 = c[i]
	elif t[i] == 3:
		if c[i] < m3:
			m3 = c[i]
print(min(m1 + m2, m3))


N = int(input())
C = list(map(int, input().split()))[:N]
T = list(map(int, input().split()))[:N]
p = q1 = q2 = 100001
for i in range(N):
	if T[i] == 3:
		p = min(p, C[i])
	elif T[i] == 2:
		q1 = min(q1, C[i])
	elif T[i] == 1:
		q2 = min(q2, C[i])
if q1 + q2 < p:
	print(q1 + q2)
else:
	print(p)


n = int(input())
n1 = [int(n) for n in input().split()]
n2 = [int(n) for n in input().split()]
d = {}
n5 = []
n6 = []
n7 = []
for i in range(len(n1)):
	a = n2[i]
	d[n1[i]] = a
for i in d:
	if d[i] == 3:
		n7.append(i)
	elif d[i] == 1:
		n5.append(i)
	else:
		n6.append(i)
for i in n5:
	for j in n6:
		a = i + j
		n7.append(a)
print(min(n7))


N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
mi1 = mi2 = mi3 = 100000
for i in range(N):
	if B[i] == 1:
		mi1 = min(A[i], mi1)
	elif B[i] == 2:
		mi2 = min(A[i], mi2)
	else:
		mi3 = min(A[i], mi3)
print(mi1 + mi2) if mi1 + mi2 < mi3 else print(mi3)


n = int(input())
a = list(map(int, input().split()))
l = list(map(int, input().split()))
m1 = 100000
m2 = 100000
m3 = 100000
for i in range(0, n):
	if l[i] == 1:
		if a[i] < m1:
			m1 = a[i]
	elif l[i] == 2:
		if a[i] < m2:
			m2 = a[i]
	elif a[i] < m3:
		m3 = a[i]
print(min(m1 + m2, m3))


n = int(input())
l1 = list(map(int, input().split()))
l2 = list(map(int, input().split()))
x1 = x2 = x3 = 100000
for i in range(len(l2)):
	if l2[i] == 3:
		x3 = min(x3, l1[i])
	elif l2[i] == 1:
		x1 = min(x1, l1[i])
	else:
		x2 = min(x2, l1[i])
print(min(x1 + x2, x3))