### 2004 Canadian Computing Competition, Stage 2

## Day 1, Problem 1: Scribble

*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 72 points, nixed (meaning "refused") is worth 26 points, flong (which is "a compressed mass of paper sheets, forming a matrix or mold for stereotype plates") is worth 18 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 33 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 7 tiles/letters and you have scores for each letter (where the score s_{α} for each letter α satistisfies 0 < `s`_{α} < 26), 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 the find the highest scoring word.

### Input

You are given a number `k` (1 ≤ `k` ≤ 7) on the first line of input. On the next k lines, you will be given triples α `s`_{α} `r`_{α}, where α is a letter, `s`_{α} is the score for that letter, and r_{α} 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 7 points. On the next (the `k` + 2nd) line, there is the number `N` (0 < `N` < 100000). On each of the next `N` lines, there is a word (you can assume the length of each word is at least one).

### Output

The output 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

All Submissions

Best Solutions

**Point Value:** 10

**Time Limit:** 2.00s

**Memory Limit:** 16M

**Added:** Dec 27, 2008

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

ImbaCalvinon Jul 07, 2013 - 9:32:42 pm UTC Data error?Also, there is a similar situation in the 3rd test case.

It may not affect C++ submissions, but it had certainly screwed my Python program...

bbi5291on Jul 07, 2013 - 11:04:27 pm UTC Re: Data error?xiaowuc1on Jun 05, 2014 - 10:55:13 pm UTC Re: Data error?In submission 180781, I terminate early if there are no more lines to read, resulting in no output for cases 3 and 9.

In submission 180782, I immediately print out my best result if there is no input to read, which gives AC.

jeffreyxiaoon Aug 19, 2014 - 3:37:11 pm UTC Re: Data error?Edit: nvm I got it

Alexon Aug 20, 2014 - 1:10:31 am UTC Re: Data error?zhxl0903on Apr 13, 2009 - 1:44:51 am UTC Could someone explain to me what the sigma does?jargonon Apr 13, 2009 - 1:57:45 pm UTC Re: Could someone explain to me what the sigma doeBasically, you're given a list of letters, their point value, and the number of them in the game. i.e.

means that there is one occurrence of letter a, each worth one point; there is one occurrence of letter b, each worth four points; there is one occurrence of letter c, each worth two points; and there are four occurrences of letter d, each worth ten points.

You're then given a list of words. Your job is to find the highest scoring word, given the letter scores. i.e.,

You would output 6, as this is the maximum score attainable.

hansonw1on Apr 13, 2009 - 2:05:14 pm UTC Re: Could someone explain to me what the sigma doe(Or, there will always be exactly 7 tiles in your hand)

hansonw1on Apr 13, 2009 - 3:02:11 pm UTC Re: Re: Could someone explain to me what the sigmazerglingrushon Jan 10, 2009 - 11:56:16 pm UTC The length actually matterstaimla101on Jan 11, 2009 - 1:50:08 am UTC Re: The length actually mattersI was just asking to possibly make my program better/faster

of course, yours is accepted and mine isn't so...

taimla101on Jan 10, 2009 - 11:21:04 pm UTC What is the maximum length of the worddAedaLon Jan 10, 2009 - 11:39:16 pm UTC Re: What is the maximum length of the wordhansonw1on Jan 11, 2009 - 12:29:28 am UTC Re: What is the maximum length of the wordAnd yes the letters are all lowercase.

taimla101on Jan 10, 2009 - 11:44:50 pm UTC will the letters be lowercase?