Submit | All submissions | Best solutions | Back to list |
TRIBE - Tribe |
English | Vietnamese |
The language of an ancient tribe was only based on two characters - a and b - to create words. It also used character space to separate words in the sentence. So, a word was an unextendible consecutive characters in a sentence. A sentence did not contain meaningless words. People in the tribe were very religious, they believed that each word had its own lucky value. The value of a sentence is the summation of the value of each word in that sentence.
You can use at most x character a, y character b and z character space to make the a sentence. Show us how lucky you are! Tell us the luckiest sentence you can make. In case of multiple solutions, print the smallest lexicographical sentence (space is smaller than a and a is smaller than b).
Input
- The first line contains N, the number of meaningful words in the language.(1 ≤ N ≤ 50)
- The second line contains 3 integer numbers:x, y, z as stated.( 0 ≤ x, y, z ≤ 50)
- Each of the next N lines contains one word and its value, separated by a space. Value of a word is a positive integer and not exceed 50.
Output
Only one line, contains the sentence you found.
Example
Input: 4 3 3 1 abb 3 baa 3 aaa 4 bbb 1 Output: abb baa
Note
- The sentence s1 is lexicographically smaller than sentence s2 if the string represents s1 is smaller than s2.
Added by: | VOJ Team |
Date: | 2008-08-01 |
Time limit: | 0.200s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 SCM qobi VB.NET |
Resource: | VNOI Marathon '08 - Round 7/DivB Problem Setter: KhĂșc Anh Tuấn |