## CCO '04 P1 - Scribble

View as PDF

Points: 5
Time limit: 1.0s
Memory limit: 32M

Problem types
##### Canadian Computing Competition: 2004 Stage 2, Day 1, Problem 1

Nixed, he placed the flong into the calathi halfway through the yuga.

Huh?

Believe it or not, the above sentence is actually a valid English sentence. It also has two other features: it looks like spam, and the words are very valuable.

Valuable, you say? (For some reason, you are doing lots of talking to yourself today).

Yes, valuable, if you are playing Scribble. In the standard game of Scribble, calathi (which means "a vase-shaped basket represented in Greek painting and sculpture") is worth points, nixed (meaning "refused") is worth points, flong (which is "a compressed mass of paper sheets, forming a matrix or mold for stereotype plates") is worth points, and yuga which is "any one of the four ages, Krita, or Satya, Treta, Dwapara, and Kali, into which the Hindus divide the duration or existence of the world" is worth points.

Specifically, as you may know, each letter in Scribble is worth a given number of points. The goal is get the most points with a given set of letters.

For this question, we will modify the game slightly. Suppose you have tiles/letters and you have scores for each letter (where the score for each letter satisfies ), and also you have a dictionary of valid words that you can consult before you play (this is different than the "normal" Scribble play). Your task is to find the highest scoring word.

#### Input Specification

You are given a number on the first line of input. On the next lines, you will be given triples , where is a letter, is the score for that letter, and is the number of times that letter occurs as a tile. You can assume that For example, the triple a 7 2 means you have two tiles marked a and each is worth points. On the next (the nd) line, there is the number . On each of the next lines, there is a word (you can assume the length of each word is at least one).

#### Output Specification

The output is one line long, containing one integer, which is the maximum score. That is, the maximum number of points that can be attained by using the tiles to form one complete word. If no word can be formed, the maximum number of points is zero.

#### Sample Input

4
a 1 1
b 4 1
c 2 1
d 10 4
3
ab
bc
c

#### Sample Output

6