using Microsoft.VisualBasic.CompilerServices; using System; using System.Collections.Generic; using System.Linq; using System.Runtime.InteropServices; namespace ConsoleApp2 { class Program { private static string input; private static string[] bookWords; private static int[] bookValue; private static void InitializeBook(int q) { bookWords = new string[q]; bookValue = new int[q]; for (int i = 0; i < q; i++) { string[] tokens = Console.ReadLine().Split(' '); bookWords[i] = tokens[0]; bookValue[i] = int.Parse(tokens[1]); } } private static int[] LettersCount(string word, int from, int to) { int[] result = new int[26]; // 26 - кол-во буква в алфавите for(int i = from; i < to; i++) { result[(int)word[i] - 97] ++; } return result; } private static int PickWords(int index) { int result = -1; for (int i = 0; i < bookWords.Length; i++) { if (bookWords[i].Length <= input.Length - index && Enumerable.SequenceEqual(LettersCount(bookWords[i], 0, bookWords[i].Length), LettersCount(input, index, index + bookWords[i].Length))) { int pathResult; if (input.Length == index + bookWords[i].Length) { pathResult = 0; } else pathResult = PickWords(index + bookWords[i].Length); if (pathResult != -1 && result == -1 || (pathResult != -1 && pathResult + bookValue[i] < result)) result = pathResult + bookValue[i]; } } return result; } static void Main(string[] args) { input = Console.ReadLine(); int result = -1; int q = int.Parse(Console.ReadLine()); InitializeBook(q); result = PickWords(0); Console.WriteLine(result); } } }