ACM-ICPC INC 2008 Qualification

Problem C

Panda Land 3: Text Wrapper

Time Limit: 5s
There's nothing interesting in Panda Land when this problem is being made. When I walked in a bamboo forest, I saw a little panda doing his essay project using IBM T60/2008-EQ7 notebook. This panda was using simple text-editor software. To write that essay on a fixed paper size, he needs to wrap some of the text manually.

Each character that appears on the essay may have different width (between 1 to 100, inclusive, and strictly smaller than the paper's width).
Ignore any newline characters that appear on the essay (It means, all the essay/input-text are treated as a single line although they may appear in several lines)
Any substring "\n" should be replaced with newline character ('\n') on the output text. Newline character has 0 width.
For each output line which exceeds the paper's width, wrap the line with the following rules:

If the word that cannot be fit is the first word on that line, then break that word by inserting a hyphen character ('-'), maximize the number of characters on that line. Hyphen character has 1 width, so make sure this character aso fit in the line. The remaining characters from the broken word should be moved to the next line.
If the word that cannot be fit is not the first word on that line, then move that word wholly to the next line (don't break the word).

For each output line which doesn't exceed the paper's width, then let it be.

Note: word is defined as a single space or a sequence of non-space character.

Help this little panda by writing a program to read his essay and output the formatted text as described above.

Input

There will be multiple test cases for this problem.

Each test case will consist of three parts. The first part is a line contains an integer L (1 <= L <= 100,000) the paper's width.

The second part will tell us each character's width in the following format:

<CHAR><SPACE><WIDTH>

Where,
<CHAR>, the character that may appear on the essay.
<SPACE>, a single space.
<WIDTH>, the character's width (between 1 to L-1, inclusive).

Characters that may appear on the essay are:
- Alphanumeric ('a'-'z', 'A', 'Z', '0'-'9')
- Space (' ')
- Backslash ('\')

The second part will be ended by "END OF LIST" on a single line.

The third part contains several lines representing the panda's essay. The number of characters that appear in the essay will not exceed 1,000,000. You may assume that every character in the essay exists in the list. This part will be ended by "END OF FILE" on a single line.

Output

Print "Case #X:" (X is the case number) at the first line of each testcase. The formatted text should be printed after that.

Sample Input

Output for Sample Input

10
A 1
B 1
c 1
d 1
e 1
  1
f 1
g 1
n 1
p 1
END OF LIST
pAndAfAndAAAA*edABAfgnppAcA****
fgnp******
END OF FILE
5
a 1
\ 1
n 1
END OF LIST
aaaa\naa
END OF FILE

Case #1:
pAndAfAnd-
AAAA*
edABAfgnp-
pAcA****
fgnp******
Case #2:
aaaa
aa

ASTERISK CHARACTER ('*') ON THE SAMPLE INPUT/OUTPUT REPRESENTS SPACE (' ') AND WILL APPEAR AS SPACE IN THE TEST CASE. ASTERISK CHARACTER IS USED THERE JUST TO MAKE SURE YOUR EYES ABLE TO LOOK AT THE DATA.

YOU MAY GET WRONG ANSWER FOR THE INCORRECT OUTPUT FORMAT ON THIS PROBLEM (NO PRESENTATION ERROR).