Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2894
Arrange the Problem Set

Time Limit: 2 Seconds      Memory Limit: 65536 KB      Special Judge

Holding a programming contest is very hard. You have to find a place that is large enough to hold the contest. You have to get a lot of balloons and arrange several pretty girls to send them. You have to prepare the gifts for the winners. You have to collect several problems and check the answers. And what's more, you have to choose some good problems and title them to set up a problem set. Facing such problems, the chief judge ask you to help him to set up a good problem set.

Given the evaluation, resources needed and the key words of each problem, your task is to choose K problems and title them to set up a problem set that satisfies the following conditions:

  • The title of each problem is composed of the key words of that problem and insignificant words.
  • The title must begin with a key word.
  • Insignificant words are not necessary.
  • Each key word can appear at most once in the title.
  • The first letter of each key word in the title must be capital letter.
  • The rest letters must be small letters.
  • The words are seperated by exactly one space.
  • Each title can not contain more than 10 words.
  • The first letters of the titles in the problem set must be in alphabetical order, ie. A, B, C...
  • The sum of the evaluation of the problems in the problem set must be maximum.
  • Under the conditions above, the total resources needed by the problem set must be minumum.


The first line of each test case contains three integers, N, M, K, indicating the number of problems you collect, the number of insignificant words and the number of problems you must choose. The second line contains the M insignificant words. The following N lines discript the N problems in the following form:
Ei Ri Pi KWi,1 KWi,2 ... KWi,Pi
where Ei is the evaluation of the i-th problem, Ri is the resources the i-th problem needs and KWi,j is a key word of the i-th problem.

The input satisfy the following constraints:

  • N will be between 1 and 1000, inclusive.
  • M will be between 0 and 1000, inclusive.
  • K will be between 1 and N, inclusive.
  • Each Ei will be between 0 and 10000, inclusive.
  • Each Ri will be between 0 and 50000, inclusive.
  • Each Pi will be between 0 and 50, inclusive.
  • Each word will contian small letters only.
  • Each word will contain no more than 20 letters.
  • All the words will be distinct.
  • A line "0 0 0" indicates the end of the input.


Output the problem list in the form of [ID] Title, one problem in a line. ID begins with 1001. If the problem set can't be set up, just output"Impossible" in one line. There must be a blank line separating two contests, but no extra line at the end of output.

Sample Input

4 5 4
a an and in of
7 8 2 ac dasher
6 9 2 beasts beauty
7 6 1 cai
6 7 1 dollars
3 0 3

1 1 2 a b
1 1 2 hello world
1 1 3 read after me
0 0 0

Sample Output

[1001] Ac Dasher
[1002] Beasts and Beauty
[1003] Cai in
[1004] Dollars


Author: GUAN, Yao
Source: ZOJ Monthly, January 2008
Submit    Status