Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2560
I Just Called ...

Time Limit: 5 Seconds      Memory Limit: 32768 KB

You are hired by CBOOPS company that is planning to create the new billing system for recently coming to the market company MegaHrun.

The country is divided to m regions that are united to n superregions. There are t towns in the country, each of them belongs to some region.

Phones numbers in the country consist of d digits. Each town has its own collection of phone codes.No code within the country is the prefix of another code. The code consists of two parts: the region code and the town code. For example, Gatchina in Leningrad region has a code 81362, here 813 is Leningrad region code and 62 is the town code. Each region has exactly one code, while the town may have several codes. For example, St Petersburg region has region code 812 and St Petersburg itself has town codes 1, 2, 3, and 5. For some regions the town code may be empty, for example, Moscow region has code 095 and Moscow itself has no additional town codes. In this case we say that the town has 0 town codes.

Each call is characterized by the region from which it was made and the town it was made to.

There are four types of calls depending on the region from which it was made. The call can be made:

      1. from home region,
      2. from home network within home superregion,
      3. from home network outside home superregion,
      4. from alien network.

The network of MegaHrunexists in several regions of the country. One of these regions is homefor the subscriber we are billing. A call from this region is of the first type. Calls from other regions covered by the network in this superregion are of the second type. Calls from covered by the network regions of other superregion are of the third type. Calls from regions not covered by the network are of the fourth type.

In turn, depending on the destination, the call can be local, regional, interregional, or long distance.

The call is local if it is made to the same town that the caller is. The call is regional if it is made to the same region. The call is interregional, if it is made to another region, covered by the network. In the other case the call is long distance.

Your task is given the tariff options for all sixteen types of calls, and the descriptions of the calls, calculate the total cost of the calls. We will only consider outgoing calls.


The first line of the input file contains t, m, n, and d (1 <= t <= 10 000, 1 <= m <= 200, 1 <= n <= 20, 2 <= d <= 1000). The following m lines describe regions, each region is described with an integer number si, the superregion it belongs to, and the sequence of at most d-1 digits, the region code.

Description contains ri, the regionthistownbelongs to, and pi, the number of town codes for this town (0 <= pi <= 100). If pi > 0, the second line contains codes of the town, separated by spaces (pi = 0 means that the town has no additional code to region code). The total length of the region code and the town code does not exceed d-1.

The next line contains h, the number of the home region of the number to bill, and z, the number of regions covered by the MegaHrunnetwork. The next line contains z integer numbers, the numbers of regions covered. The home region is guaranteed to be covered.

The following four lines contain four integer numbers each, the cost per minute of the local, regional, interregional, and long distance call for calls from home, home within superregion, home outside superregion, and alien network respectively (costs are positive and do not exceed 100000).

The next line contains c, the number of calls made (1 <= c <= 10000). Each of the following c lines contains an integer number ti, the town from which the call was made, d digits, the phone number of the call, and li, the length of the call in minutes (1 <= li <= 1000). If the phone number does not belong to any of the towns, it is considered wrong and costs nothing.


Output the total cost of all calls.

Sample Input:
6 4 2 10
1 812
1 813
2 095
2 096
1 4
1 2 3 5
1 1
2 1
2 2
6133 614
3 0
4 2
11 12
1 2
1 3
10 20 30 40
20 40 50 60
30 30 30 30
60 70 100 120
1 8121234567 10
1 8136255555 1
1 8136133333 5
1 8136139999 1
1 0953456789 5
1 0961234567 5
1 0969876543 4
2 8121234567 20
2 8136134567 5
5 8121234567 10
5 0953456789 5
6 0957654321 4
6 8121234567 20
Sample Output:

Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #4
Submit    Status