[BOJ] 16508. 전공책

import java.util.Scanner;

public class Main {
	static int N; 
	static int values[];
	static int wordCount[];
	static int bookCount[];
	static String books[]; 
	static String word;
	static int answer = Integer.MAX_VALUE;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		word = sc.next();
		N = sc.nextInt();
		values = new int[N];
		books = new String[N];
		
		for(int i = 0; i < N; i++) {
			values[i] = sc.nextInt();
			books[i] = sc.next();
		}
		
		wordCount = new int[26];
		for(int i = 0; i < word.length(); i++) {
			wordCount[word.charAt(i)-'A']++;
		}
		bookCount = new int[26];
		dfs(0,0);
		if(answer == Integer.MAX_VALUE) System.out.println(-1);
		else System.out.println(answer);
	}
	
	public static void dfs(int depth, int sum) {
		if(depth == N) {
			if(isOk()) {
				answer = Math.min(answer, sum);
			}				
			return;
		}
		
		for(int i = 0; i < books[depth].length(); i++) {
			bookCount[books[depth].charAt(i)-'A']++;
		}
		dfs(depth+1, sum + values[depth]);
		for(int i = 0; i < books[depth].length(); i++) {
			bookCount[books[depth].charAt(i)-'A']--;
		}
		dfs(depth+1, sum);		
		
	}
	
	public static boolean isOk() {
		for(int i = 0; i < word.length(); i++) {
			if(bookCount[word.charAt(i)-'A'] < wordCount[word.charAt(i)-'A']) return false;
		}
		return true;
	}
}