L. Let's Go Yum Cha
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

At a Hong Kong tea house, the bill for a table consists of the tea charge, the dim sum charges, and possibly a $$$10\%$$$ service charge, commonly called plus one.

Each kind of tea has a price per person. Everyone at the same table chooses the same kind of tea, and the tea charge is the number of people multiplied by the price of that tea per person.

Every dim sum dish belongs to exactly one of five price categories. All dishes in the same category have the same price.

TokenCategory
SMALLSmall
MEDIUMMedium
LARGELarge
SPECIALSpecial
DELUXEDeluxe

For each table, calculate the bill in the following order:

  1. Charge the per-person price of the selected tea once for each of the $$$n$$$ people at the table.
  2. For each order record, find the price category of the named dish, then charge that category's price once for each serving in the record. The same dish may appear in more than one order record, and every record must be counted.
  3. Add all tea and dim sum charges to obtain the subtotal.
  4. If $$$w=1$$$, the service charge is waived and the subtotal is the final bill. Otherwise, add a $$$10\%$$$ service charge to the entire subtotal. Round the resulting total to the nearest integer Hong Kong dollar; if it is exactly halfway between two integers, round upward.

Given the menu and the orders of several tables, determine the final bill for every table.

Input

The first line contains an integer $$$T$$$ ($$$1\le T\le 1000$$$), the number of kinds of tea.

Each of the next $$$T$$$ lines contains a string $$$t_i$$$ and an integer $$$a_i$$$ ($$$1\le a_i\le 1000$$$), denoting the name and the price per person of tea $$$i$$$.

The next line contains five integers $$$b_{\mathrm{SMALL}}$$$, $$$b_{\mathrm{MEDIUM}}$$$, $$$b_{\mathrm{LARGE}}$$$, $$$b_{\mathrm{SPECIAL}}$$$, and $$$b_{\mathrm{DELUXE}}$$$ ($$$1\le b_{\mathrm{SMALL}},b_{\mathrm{MEDIUM}},b_{\mathrm{LARGE}},b_{\mathrm{SPECIAL}},b_{\mathrm{DELUXE}}\le 1000$$$), the prices of the five categories in exactly this order. These prices are not necessarily increasing.

The next line contains an integer $$$D$$$ ($$$1\le D\le 1000$$$), the number of dim sum dishes.

Each of the next $$$D$$$ lines contains two strings $$$d_i$$$ and $$$c_i$$$, denoting the name and the category of dim sum dish $$$i$$$. $$$c_i$$$ is one of SMALL, MEDIUM, LARGE, SPECIAL, and DELUXE.

The next line contains an integer $$$m$$$ ($$$1\le m\le 1000$$$), the number of tables.

For each table:

  • The first line contains an integer $$$n$$$, a string $$$t$$$, an integer $$$k$$$, and an integer $$$w$$$ ($$$1\le n\le 1000$$$, $$$0\le k\le 1000$$$, $$$w\in\{0,1\}$$$). They denote the number of people, the selected tea's name, the number of order records, and whether the service charge is waived, respectively. If $$$w=1$$$, the service charge is waived; if $$$w=0$$$, it is charged.
  • Each of the next $$$k$$$ lines contains a string $$$d_j$$$ and an integer $$$q_j$$$ ($$$1\le q_j\le 1000$$$), denoting that order record $$$j$$$ orders $$$q_j$$$ servings of dish $$$d_j$$$.

It is guaranteed that the sum of $$$k$$$ over all tables does not exceed $$$1000$$$.

Every tea name and dish name consists of $$$1$$$ to $$$20$$$ uppercase English letters, lowercase English letters, or underscores. Names are case-sensitive. Tea names are pairwise distinct, and dish names are pairwise distinct. Every referenced tea and dish is present in the menu.

Output

Print $$$m$$$ lines. The $$$i$$$-th line must contain one integer: the final bill of table $$$i$$$ in Hong Kong dollars.

Example
Input
2
Pu_Er 8
Jasmine 10
20 24 28 32 45
6
Har_Gow DELUXE
Siu_Mai LARGE
Char_Siu_Bao MEDIUM
Spring_Roll SMALL
Egg_Tart SPECIAL
Custard_Bun DELUXE
3
3 Pu_Er 4 0
Har_Gow 2
Siu_Mai 1
Har_Gow 1
Egg_Tart 2
2 Jasmine 2 1
Char_Siu_Bao 2
Spring_Roll 3
1 Jasmine 3 0
Custard_Bun 1
Spring_Roll 1
Spring_Roll 1
Output
276
128
105
Note

For the first table, the tea charge is $$$3\cdot 8=24$$$. Its dim sum charges total $$$3\cdot45+1\cdot28+2\cdot32=227$$$, so the subtotal is $$$251$$$. The service charge is not waived, and the final bill is $$$276$$$ after rounding.

For the second table, the subtotal is $$$2\cdot10+2\cdot24+3\cdot20=128$$$. The service charge is waived, so the final bill is $$$128$$$.

For the third table, the subtotal is $$$1\cdot10+1\cdot45+2\cdot20=95$$$. The service charge is not waived. The total is exactly halfway between $$$104$$$ and $$$105$$$, so it is rounded upward to $$$105$$$.

Photo by Little Cyan Fish in Hong Kong, July 2026