Berland shop sells $n$ kinds of juices. Each juice has its price $c_i$. Each juice includes some set of vitamins in it. There are three types of vitamins: vitamin "A", vitamin "B" and vitamin "C". Each juice can contain one, two or all three types of vitamins in it.

Petya knows that he needs all three types of vitamins to stay healthy. What is the minimum total price of juices that Petya has to buy to obtain all three vitamins? Petya obtains some vitamin if he buys at least one juice containing it and drinks it.


-----Input-----

The first line contains a single integer $n$ $(1 \le n \le 1\,000)$ — the number of juices.

Each of the next $n$ lines contains an integer $c_i$ $(1 \le c_i \le 100\,000)$ and a string $s_i$ — the price of the $i$-th juice and the vitamins it contains. String $s_i$ contains from $1$ to $3$ characters, and the only possible characters are "A", "B" and "C". It is guaranteed that each letter appears no more than once in each string $s_i$. The order of letters in strings $s_i$ is arbitrary.


-----Output-----

Print -1 if there is no way to obtain all three vitamins. Otherwise print the minimum total price of juices that Petya has to buy to obtain all three vitamins.


-----Examples-----
Input
4
5 C
6 B
16 BAC
4 A

Output
15

Input
2
10 AB
15 BA

Output
-1

Input
5
10 A
9 BC
11 CA
4 A
5 B

Output
13

Input
6
100 A
355 BCA
150 BC
160 AC
180 B
190 CA

Output
250

Input
2
5 BA
11 CB

Output
16



-----Note-----

In the first example Petya buys the first, the second and the fourth juice. He spends $5 + 6 + 4 = 15$ and obtains all three vitamins. He can also buy just the third juice and obtain three vitamins, but its cost is $16$, which isn't optimal.

In the second example Petya can't obtain all three vitamins, as no juice contains vitamin "C".

Difficulty: interview

Starter code:

Solutions:
n = int(input())

def func(v):
    res = 0
    if "A" in v: res |= 1
    if "B" in v: res |= 2
    if "C" in v: res |= 4
    return res

cost = [10 ** 10] * 8
cost[0] = 0
for _ in range(n):
    c, v = input().split()
    c = int(c)
    v = func(v)
    for i in range(8):
        cost[i | v] = min(cost[i | v], cost[i] + c)

print(cost[7] if cost[7] < 10 ** 10 else -1)


n = int(input())


costs = [10 ** 18 for i in range(1 << 3)]

for i in range(n):
    cs, s = input().split()
    cs = int(cs)

    msk = 0
    if 'A' in s:
        msk |= 1
    if 'B' in s:
        msk |= 2
    if 'C' in s:
        msk |= 4

    costs[msk] = min(costs[msk], cs)


for msk in [3, 5, 6, 7]:
    for m1 in range(8):
        for m2 in range(8):
            if (m1 | m2) == msk:
                costs[msk] = min(costs[msk], costs[m1] + costs[m2])


if costs[7] == 10 ** 18:
    print(-1)
else:
    print(costs[7])


#      
import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        print(*args, **kwargs, file=sys.stderr)
    dprint('debug mode')
except Exception:
    def dprint(*args, **kwargs):
        pass



inId = 0
outId = 0
if inId>0:
    dprint('use input', inId)
    sys.stdin = open('input'+ str(inId) + '.txt', 'r') #标准输出重定向至文件
if outId>0:
    dprint('use output', outId)
    sys.stdout = open('stdout'+ str(outId) + '.txt', 'w') #标准输出重定向至文件
    atexit.register(lambda :sys.stdout.close())     #idle 中不会执行 atexit
    
N, = getIntList()

dp = [ 10** 10 for i in range(10)]
dp[0] = 0
for _ in range(N):
    g = input().split()
    p = int(g[0])
    v = g[1]
    t = 0
    c = 0
    for x in 'ABC':
        if x in v:
            t = t | (1<<c)
        c+=1
    for i in range(8):
        if dp[i] + p < dp[ i | t]:
            dp[i | t] = dp[i] + p

if dp[7] == 10 **10:
    print(-1)
else:
    print(dp[7])



def mi():
	return map(int, input().split())

n = int(input())
a = [0]*n
for i in range(n):
	a[i] = list(input().split())
	a[i][0] = int(a[i][0])
	#print (''.join(sorted(list(a[i][1]))))

A,B,C,AB,AC,BC,ABC = 1e10,1e10,1e10,1e10,1e10,1e10,1e10
for i in range(n):
	a[i][1] = ''.join(sorted(list(a[i][1])))
	if a[i][1]=='A':
		A = min(A,a[i][0])
	if a[i][1]=='AB':
		AB = min(AB,a[i][0])
	if a[i][1]=='AC':
		AC = min(AC,a[i][0])
	if a[i][1]=='BC':
		BC = min(BC,a[i][0])
	if a[i][1]=='ABC':
		ABC = min(ABC,a[i][0])
	if a[i][1]=='B':
		B = min(B,a[i][0])
	if a[i][1]=='C':
		C = min(C,a[i][0])
t = [AB+C, AB+AC, AB+BC, AB+ABC, BC+A, BC+AB, BC+AC, BC+ABC, AC+B, AC+AB, AC+BC, AC+ABC, ABC, A+B+C]
lol = min(t)
if lol==1e10:
	print (-1)
else:
	print(lol)

from sys import stdin, stdout


n = int(stdin.readline())
mp = {}

for i in range(n):
    c, s = stdin.readline().strip().split()
    s = ''.join(sorted(list(s)))
    
    
    c = int(c)
    if not s in mp:
        mp[s] = c
    else:
        mp[s] = min(mp[s], c)

ans = float('inf')
for v in mp:
    for c in mp:
        for g in mp:
            if len({v, c, g}) != 3:
                continue
            
            if len(set(list(v)) | set(list(c)) | set(list(g))) != 3:
                continue
            
            ans = min(ans, mp[v] + mp[c] + mp[g])



for c in mp:
    for g in mp:
        if len({c, g}) != 2:
            continue
        
        if len(set(list(c)) | set(list(g))) != 3:
            continue
        
        ans = min(ans, mp[c] + mp[g])


for v in mp:
    
    if len(set(list(v))) != 3:
        continue
    
    ans = min(ans, mp[v])            
            

if ans == float('inf'):
    stdout.write('-1\n')
else:
    stdout.write(str(ans))

from collections import defaultdict

n = int(input())
inf = float('inf')
mins = defaultdict(lambda: inf)
for _ in range(n):
    ci, vit = input().split()
    ci = int(ci)
    vit = "".join(sorted(vit))
    mins[vit] = min(mins[vit], ci)

result = min(
    mins["A"] + min(min(mins["B"], mins["AB"]) + min(mins["C"], mins["AC"]), mins["BC"]),
    mins["B"] + min(min(mins["A"], mins["AB"]) + min(mins["C"], mins["BC"]), mins["AC"]),
    mins["C"] + min(min(mins["A"], mins["AC"]) + min(mins["B"], mins["BC"]), mins["AB"]),
    mins["AB"] + min(mins["C"], mins["AC"], mins["BC"]),
    mins["AC"] + min(mins["B"], mins["AB"], mins["BC"]),
    mins["BC"] + min(mins["A"], mins["AB"], mins["AC"]),
    mins["ABC"],
)
print(-1 if result == inf else result)


import sys


def __starting_point():
    n = int(next(sys.stdin))

    optimal = {ele: float('inf') for ele in \
            [(1,0,0), (0,1,0), (0,0,1),
             (1,1,0), (1,0,1), (0,1,1),
             (1,1,1)]}
    optimal[(0,0,0)] = 0

    for _ in range(n):
        price, vitamin = next(sys.stdin).strip().split()
        price = int(price)

        state = (
                    int('A' in vitamin), 
                    int('B' in vitamin), 
                    int('C' in vitamin)
                )

        for a in range(2):
            for b in range(2):
                for c in range(2):
                    if optimal[(a,b,c)] < float('inf'):
                        new_state = (a|state[0], b|state[1], c|state[2])
                        optimal[new_state] = \
                                min(optimal[new_state], optimal[(a,b,c)]+price)
    print(-1 if optimal[(1,1,1)] == float('inf') else optimal[(1,1,1)])

        

__starting_point()

n = int(input())
c = []
s = []
for _ in range(n):
    ln = input().split()
    c.append(int(ln[0]))
    s.append(str(ln[1]))
dp = [1e9 for _ in range(8)]
dp[0] = 0
for i in range(n):
    k = 0
    if 'A' in s[i]:
        k += 1
    if 'B' in s[i]:
        k += 2
    if 'C' in s[i]:
        k += 4
    for j in range(8):
        dp[j | k] = min(dp[j | k], dp[j] + c[i])
if dp[7] == 1e9:
    print(-1)
else:
    print(dp[7])


n = int(input())

cs = []
vs = []

for i in range(n):
    c, v = input().split(' ')
    c = int(c)

    cs += [c]
    vs += [set(v)]

BigInt = 10 ** 10
ans = BigInt

for opt in ['A|B|C', 'AB|C', 'AC|B', 'BC|A', 'ABC']:
    opt = [set(s) for s in opt.split('|')]
    cur = 0

    for group in opt:
        minCost = BigInt

        for c, v in zip(cs, vs):
            if v.issuperset(group) and c < minCost:
                minCost = c

        if minCost == BigInt:
            cur = BigInt
            break

        cur += minCost

    if cur < ans:
        ans = cur

    #print(opt, cur)
    
print(-1 if ans == BigInt else ans)

import math
n = int(input())
inf = float("inf")
a = [inf]
b = [inf]
c = [inf]
ab = [inf]
ac = [inf]
bc = [inf]
abc = [inf]
for i in range(n):
  x,s = input().split()
  x = int(x)
  s_  = []
  for j in s:
    s_.append(j)
  s = sorted(s_)
  s = "".join(s)
  if s == "A":
    a.append(x)
  elif s == "B":
    b.append(x)
  elif s == "C":
    c.append(x)
  elif s == "AB":
    ab.append(x)
  elif s == "AC":
    ac.append(x)
  elif s == "BC":
    bc.append(x)
  elif s == "ABC":
    abc.append(x)
ans = float("inf")
a = min(a)
b = min(b)
c = min(c)
ab = min(ab)
ac = min(ac)
bc = min(bc)
abc = min(abc)
ans = min(a+b+c,a+bc,b+ac,c+ab,ab+ac,ab+bc,ac+bc,abc)
if ans == inf:
  print(-1)
else:
  print(ans)

USE_STDIO = False

if not USE_STDIO:
    try: import mypc
    except: pass

def parse(s):
    r = 0
    for c in s:
        r |= 1 << (ord(c) - ord('A'))
    return r

def main():
    n,  = list(map(int, input().split(' ')))
    INF = 1000000000
    mp = [0] + [INF] * 7
    for _ in range(n):
        c, s =  input().split(' ')
        c, s = int(c), parse(s)
        for i in range(8):
            mp[i|s] = min(mp[i|s], mp[i] + c)
    print(mp[-1] if mp[-1] < INF else -1)


def __starting_point():
    main()




__starting_point()

# ns=[int(x)for x in input().split()]
n=int(input())
d={}
for _ in range(n):
    s=input().split()
    p=int(s[0])
    s[1]=list(s[1])
    s[1].sort()
    s[1]=''.join(s[1])
    # s[1]=s[1].sort()
    if s[1] in d:
        d[s[1]]=min(d[s[1]],p)
    else:
        d[s[1]]=p
def get(s):
    if s in d:
        return d[s]
    return 10**6
a=get('A')
b=get('B')
c=get('C')
ab=get('AB')
bc=get('BC')
ac=get('AC')
abc=get('ABC')
ans=min(a+b+c,a+bc,b+ac,c+ab,abc,ab+bc,ab+ac,ac+bc)
if ans<10**6:
    print(ans)
else:
    print(-1)

n=int(input())
d = {'A':float('Inf'), 'B':float('Inf'), 'C':float('Inf'), 'AB':float('Inf'), 'AC':float('Inf'), 'BC':float('Inf'), 'ABC':float('Inf')}
for i in range(n):
    r = input().split()
    c = int(r[0])
    s = r[1]
    s = ''.join(sorted([x for x in s]))
    d[s] = min(d[s], c)
ans = min(d['ABC'], d['A']+d['BC'], d['AB']+d['BC'],d['AB']+d['AC'], d['AC']+d['BC'], d['B']+d['AC'], d['C']+d['AB'], d['A']+d['B']+d['C'])
if ans < float('Inf'):
    print(ans)
else:
    print(-1)

from math import log2
pricey = 9**99
x = set()
match = ["A", "B", "C", "AB", "BC", "AC", "ABC"]
n = int(input())
cheapest = [100001]*7
for i in range(n):
    p, s = input().split()
    p = int(p)
    for c in s: x.add(c)
    s = "".join(sorted(list(s)))
    j = match.index(s)
    cheapest[j] = min(cheapest[j], p)
if len(x) < 3: print(-1)
else:
    for i in range(1, 128):
        truth = [int(i) for i in "0"*(6-int(log2(i))) + bin(i)[2:]]
        price = 0
        has = set()
        for j, b in enumerate(truth):
            if b:
                if cheapest[j] > 100000: break
                else:
                    price += cheapest[j]
                    for c in match[j]: has.add(c)
        else:
            if len(has) == 3:
                pricey = min(price, pricey)
    print(pricey)
            
                    
                    
        


#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import time

max = 300000+5

ABC = max
AC  = max
AB  = max
BC  = max
A   = max
B   = max
C   = max

n   = int(input())

for i in range(n):
    (c, s) = (i for i in input().split())
    c = int(c)
    if len(s) == 3:
        if c < ABC:
            ABC = c
    elif len(s) == 2:
        if 'A' in s:
            if 'B' in s:
                if c < AB:
                    AB = c
            else:
                if c < AC:
                    AC = c
        else:
            if c < BC:
                BC = c
    else:
        if s == "A":
            if c < A:
                A = c
        elif s == "B":
            if c < B:
                B = c
        else:
            if c < C:
                C = c

start = time.time()

ans = min (ABC, AB+C, AC+B, BC+A, AB+BC, AB+AC, BC+AC, A+B+C)

if ans == max:
    print(-1)
else:
    print(ans)
finish = time.time()
#print(finish - start)


n = int(input())
import collections
l = collections.defaultdict(list)
x = []
f1,f2,f3 = 0,0,0
for i in range(n):
	c,s = input().split()
	c = int(c)
	s = ''.join(sorted(s))
	z = [i for i in s]
	if('A' in z):
		f1 = 1
	if('B' in z):
		f2 = 1
	if('C' in z):
		f3 = 1
	l[s].append(c)
	x.append(s)
if(not(f1 and f2 and f3)):
	print(-1)
	return
for i in x:
	l[i].sort()

t1,t2,t3,t4,t5,t6,t7,t8 = 10**9,10**9,10**9,10**9,10**9,10**9,10**9,10**9
if(l['A'] and l['B'] and l['C']):
	t1 = l['A'][0] + l['B'][0] + l['C'][0]
if(l['AB'] and l['BC']):
	t2 = l['AB'][0] + l['BC'][0]
if(l['AB'] and l['AC']):
	t3 = l['AB'][0] + l['AC'][0]
if(l['AC'] and l['BC']):
	t4 = l['AC'][0] + l['BC'][0]
if(l['ABC']):
	t5 = l['ABC'][0]
if(l['A'] and l['BC']):
	t6 = l['A'][0] + l['BC'][0]
if(l['AC'] and l['B']):
	t7 = l['AC'][0] + l['B'][0]
if(l['AB'] and l['C']):
	t8 = l['AB'][0] + l['C'][0]
print(min(t1,t2,t3,t4,t5,t6,t7,t8))


import sys

n=int(input())
CS=[list(input().split()) for i in range(n)]

LIST=[10**6]*7#A,B,C,AB,BC,AC,ABC


for cs in CS:
    if "A" in cs[1]:
        LIST[0]=min(LIST[0],int(cs[0]))
    if "B" in cs[1]:
        LIST[1]=min(LIST[1],int(cs[0]))
    if "C" in cs[1]:
        LIST[2]=min(LIST[2],int(cs[0]))
    if "A" in cs[1] and "B" in cs[1]:
        LIST[3]=min(LIST[3],int(cs[0]))
    if "B" in cs[1] and "C" in cs[1]:
        LIST[4]=min(LIST[4],int(cs[0]))
    if "C" in cs[1] and "A" in cs[1]:
        LIST[5]=min(LIST[5],int(cs[0]))
    if "A" in cs[1] and "B" in cs[1] and "C" in cs[1]:
        LIST[6]=min(LIST[6],int(cs[0]))

if LIST[0]==10**6 or LIST[1]==10**6 or LIST[2]==10**6:
    print(-1)

else:
    print(min(LIST[0]+LIST[1]+LIST[2],LIST[0]+LIST[4],LIST[1]+LIST[5],LIST[2]+LIST[3],LIST[6]))


N = int(input())
src = [input().split() for i in range(N)]

INF = float('inf')
dp = [INF] * 8
dp[0] = 0
for n,vs in src:
    n = int(n)
    b = int('A' in vs) * 4
    b += int('B' in vs) * 2
    b += int('C' in vs) * 1
    dp2 = dp[:]
    for i,c in enumerate(dp):
        dp2[i|b] = min(dp2[i|b], c + n)
    dp = dp2

print(-1 if dp[-1] == INF else dp[-1])


n = int(input())
inf = 10 ** 6
abc = [inf] * 7
u = []
def rf(x, y):
    if x > y:
        return(y)
    return (x)
for i in range(n):
    k, s = input().split()
    k = int(k)
    s = list(s)
    s.sort()
    a = 'A' in s
    b = 'B' in s
    c = 'C' in s
    #print(a, b, c)
    if a: abc[0] = rf(abc[0], k)
    if b: abc[1] = rf(abc[1], k)
    if c: abc[2] = rf(abc[2], k)
    if a and b: abc[3] = rf(abc[3], k)
    if c and b: abc[4] = rf(abc[4], k)
    if a and c: abc[5] = rf(abc[5], k)
    if a and b and c: abc[6] = rf(abc[6], k)
a1 = [0] * 5
a1[0] = abc[0] + abc[1] + abc[2]
a1[1] = abc[0] + abc[4]
a1[2] = abc[1] + abc[5]
a1[3] = abc[2] + abc[3]
a1[4] = abc[6]
ans = min(a1)
if ans == inf:
    print(-1)
else:
    print(ans)


n=int(input())
d={'A':10e9,'B':10e9,'C':10e9,'AB':10e9,'BC':10e9,'AC':10e9,'ABC':10e9}
for i in range(n):
    a,b=input().split()
    a=int(a)
    b=''.join(sorted(list(b)))
    d[b]=min(d.get(b),a)
k=min(d['A']+d['B']+d['C'],d['AB']+d['BC'],d['BC']+d['AC'],d['AB']+d['AC'],d['ABC'],d['BC']+d['A'],d['AB']+d['C'],d['AC']+d['B'])
if k>=10e9:
    print(-1)
else:
    print(k)


d = {}

n = int(input())
for i in range(n):
    c, v = [j for j in input().split()]
    v = "".join(sorted(v))
    c = int(c)
    #print(v)
    if v not in d:
        d[v] = c
    else:
        if d[v] > c:
            d[v] = c

u = [("", 0)] + [(k, v) for k, v in list(d.items())]

res = 1000000000
for i1 in range(len(u)):
    for i2 in range(len(u)):
        for i3 in range(len(u)):
            s = u[i1][0] + u[i2][0] + u[i3][0]
            if "A" in s and "B" in s and "C" in s:
                co = u[i1][1] + u[i2][1] + u[i3][1]
                res = min(res, co)

if res == 1000000000:
    print(-1)
else:
    print(res)
                
            
    


n = int(input())
dic = {}
dic["A"] = float("inf")
dic["B"] = float("inf")
dic["C"] = float("inf")
dic["AB"] = float("inf")
dic["BC"] = float("inf")
dic["AC"] = float("inf")
dic["ABC"] = float("inf")
for i in range(n):
    c, s = input().split()
    c = int(c)
    s = "".join(sorted(s))
    dic[s] = min(dic[s], c)


q = float("inf")
q = min(q, dic["A"] + dic["B"] + dic["C"])
q = min(q, dic["A"] + dic["BC"])
q = min(q, dic["B"] + dic["AC"])
q = min(q, dic["C"] + dic["AB"])
q = min(q, dic["AB"] + dic["BC"])
q = min(q, dic["AC"] + dic["BC"])
q = min(q, dic["AC"] + dic["AB"])
q = min(q, dic["ABC"])

if q == float("inf"):
    print(-1)
else:
    print(q)

n = int(input())

isC = False
isB = False
isA = False

d = {}

for i in range(n):
	line = input()

	c = int(line.split(' ')[0])
	s = line.split(' ')[1]

	if 'A' in s:
		isA = True

	if 'B' in s:
		isB = True

	if 'C' in s:
		isC = True

	# print(s)

	name = ''.join(sorted(s))

	try:
		d[name] = min(c, d[name])

	except:
		d[name] = c

if not isA or not isB or not isC:
	print(-1)

else:
	arr = []

	try:
		arr.append(d['A'] + d['B'] + d['C'])
	except:
		pass

	try:
		arr.append(d['A'] + d['BC'])
	except:
		pass

	try:
		arr.append(d['AB'] + d['C'])
	except:
		pass

	try:
		arr.append(d['AC'] + d['B'])
	except:
		pass

	try:
		arr.append(d['AB'] + d['BC'])
	except:
		pass

	try:
		arr.append(d['AC'] + d['BC'])
	except:
		pass

	try:
		arr.append(d['AB'] + d['AC'])
	except:
		pass

	try:
		arr.append(d['ABC'])
	except:
		pass

	try:
		arr.append(d['ABC'])
	except:
		pass

	print(min(arr))



list_keys = ['A', 'B', 'C', 'AB', 'BC', 'AC', 'ABC', '1', '2']

def sortStr(s):
    res = ''
    s = sorted(s)
    for c in s:
        res += c
    return res

def check(s1, s2 ,s3):
    s = s1 + s2 + s3
    return 'A' in s and 'B' in s and 'C' in s

val = {}
INF = 1e9
for key in list_keys:
    val[key] = INF
val['1'] = 0
val['2'] = 0

n = int(input())
for i in range(n):
    v, s = input().split()
    v = int(v)
    s = sortStr(s)
    if val[s] > v:
        val[s] = v

res = INF
for key1 in list_keys:
    for key2 in list_keys:
        for key3 in list_keys:
            if check(key1, key2, key3):
                res = min(res, val[key1] + val[key2] + val[key3])

if res == INF:
    res = -1
print(res)

n = int(input())
price = []
vita = []
dmin = {}
dmin['A'] = 9999999
dmin['B'] = 9999999
dmin['C'] = 9999999
dmin['AB'] = 9999999
dmin['AC'] = 9999999
dmin['BC'] = 9999999
dmin['ABC'] = 9999999
for i in range(n):
    p,v = input().split()
    # price.append(int(p))
    p = int(p)
    v = ''.join(sorted(v))
    if dmin[v] > p:
        dmin[v] = p
    vita.append((p,v))
th1 = dmin['A']+dmin['B']+dmin['C']
th2 = dmin['A']+dmin['BC']
th3 = dmin['B']+dmin['AC']
th4 = dmin['C']+dmin['AB']
th5 = dmin['ABC']
th6 = dmin['AB']+dmin['BC']
th7 = dmin['AC']+dmin['BC']
th8 = dmin['AB']+dmin['AC']
res = min(th1,th2,th3,th4,th5,th6,th7,th8)
if res == 9999999:
    print(-1)
else:
    print(res)