One man launched a lottery game and wants to make money from it. Customers can buy lottery tickets online. Every ticket has a 12-digit number, each with a value from 0 to 9. Every night, there is a lucky draw. In the draw, the owner generates a lucky ticket number. According to the game rules, the winning customer will be given prize money.

The game rule: There are 3 types of lottery tickets: 1. Straight 2. Ramble 3. Lucky

Rule for Straight: In order to get prize, the lottery tickets number should be exactly matched with the lucky ticket number.

The rule for Ramble: Both the lucky ticket number and the customer's lottery ticket numbers will be sorted in ascending order. After that, if the customer's ticket number exactly matches the lucky ticket number will get the prize.

Rule for Lucky: The number of matched digits with the lucky ticket number will be counted and will be prized accordingly. Example: Customer ticket number: 683819280374 and Lucky Ticket Number: 784623819337. Here 2 positions matched: 2nd and 10th. If there is any prize for 2 matches then the customer will get that price.

Game Configuration: For straight and ramble there are no configurations. But for lucky, the owner can set some configurations. For each configuration, there will be 2 inputs: number of matches, and prize money.

As the owner tries to get maximum profit from the business, your task is to build a system that can generate a lucky ticket number so that the owner needs to give the minimum amount of prize money(0 if possible) to the customers.

Input: The first line of the input contains n, number of tickets customer brought.

For each of n line, there will be 2 strings ticket_number and ticket_type

Then there will be an integer x, the number of game configuration

For each of x line, there will be 2 integers, number_of_match, and prize_money

After that an integer s_prize as prize money for Straight

An integer r_prize as prize money for Ramble

Output: One string: A 12 digit lucky ticket number.

Sample Input:
5
908376452312 Straight
893749234434 Lucky
234739422308 Straight
347923749722 Lucky
328749273492 Ramble
3
3 300
5 500
7 800
2000
900

Some clarity according to the sample input: The customer with a lottery that has 4 digits matches with the lucky ticket number will get prize money of 300. If the lottery has 7 digits match then the prize money will be 800.

You should generate a lucky ticket number so that the owner can give the minimum possible prize money to the customers.

This is a problem facing my project. Need an optimized approach to generate the lucky ticket number. [The input dataset can be quite large]