ZOJ Problem Set - 3797
Academy City is a certain scientific place which consists of several schools and institutions of higher learning, from kindergarten to university level that learn side-by-side along with the scientists who research on psychic powers and higher technology. It is the most advanced city in the world and its technology is said to be 30 years ahead of the world.
In the city, a secret experiment called Radio Noise Project has been in progress for several years. This project is intended to utilize clones of Misaka Mikoto - a top level esper, for military purposes. These clones are also called Sisters. They can control the bioelectrical signal of the body and reroute it to a conntected nerve signal network, or the Misaka Network, which is like the Internet. Because of this, the Sisters can share and transmit information among them, and carry out large-scale scientific computation.
According to rumors, there are 20,001 Sisters distributed all around the globe. But in fact, the number of Sisters is M, since the project was divided into multiple parts and distributed over several institutions. Therefore the actual number of Sisters is only known to the top researchers like you. The last Sister (M-th) is a special one. Her name is Last Order, and she functions as the command center of the Misaka clones and the administrator of the Misaka Network.
To protect the important research data, each Sisters, including Last Order, has a unique SSH (Sister's Special Hobby) access key. If you don't have the key, any queries send to the Sisters will be ignored. The access key is generated from a key table, which consists of N types of characters, each type of character Ci appeared Ti times in the table.
The i-th Sister's access key is the i-th lexicographical largest string that can be constructed from the table. To construct the access key, you should choose at least L characters from the key table and concatenate them into a string. There is no constraints about the order of characters you constructed.
As a kind researcher, you learned these secret details about the Sisters and you feel very sympathy for Misaka Mikoto. You want to find out the SSH access key of Last Order so that you can gain control of the Misaka Network to help Misaka Mikoto stop this inhumane experiment.
There are multiple test cases. For each test case:
The first line contains three integers N (1 <= N <= 36), M (1 <= M <= 10 ^ 18) and L (0 <= L <= 360). Then followed by N lines, each line contains a character Ci and an integer Ti (1 <= Ti <= 10), Ci will be distinct and only comes from capital letters or decimal digit characters.
For each test case, output the SSH access key of Last Order. If the key not exists, output -1 instead.
3 37 1 I 1 P 1 C 5 18 7304020889161 18 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 A 1 C 1 D 1 E 1 Q 1 S 1 W 1 X 1 Z 1
Author: JIANG, Kai
Source: ZOJ Monthly, June 2014