BOJ - 16508 - 전공책

import sys

def checkBook(word, book, price):
    cnt = 0
    for w in word:
        if w in book:
            cnt += 1
            book = book.replace(w, ' ', 1)
            if cnt == len(word):
                return price
    return sys.maxsize

def solution():
    ret = []
    T = sys.stdin.readline().strip()
    N = int(sys.stdin.readline())
    price = []
    book = []
    for _ in range(N):
        p, b = map(str, sys.stdin.readline().split())
        price.append(int(p))
        book.append(b)

    for i in range(1 << len(book)):
        searchString = ""
        sumPrice = 0
        for j in range(len(book)):
            if (i & 1 << j) != 0:
                searchString += book[j]
                sumPrice += price[j]
        ret.append(checkBook(T, searchString, sumPrice))

    ret = min(ret)
    if ret == sys.maxsize:
        ret = -1

    print(ret)

solution()

https://www.acmicpc.net/problem/16508