Batera’s House
By Matheus Pimenta, UNB 
Brazil
By Matheus Pimenta, UNB Brazil
Batera's House is a place where a lot of things happen. That's where ideas like “bora pra chapada, neném?? - Dudu” come from. It is also a place where a lot of slangs are used, such as "pô deivis, mas bem que seria bom...", or "beeeeeem ...". And it is also where many nicknames are created, such as "Pimenta Filosofal", "Pai Alan", "Jonny Boy", "Pimenta Marinho" and the best nickname of all: "João Henrique".
The boys are playing the RPG invented by Dôdo and Leo. The game consists of capturing monsters, training them and using them in battles. At this point, we are entering a map where there are several "neutral" locations, labeled 1 to V. In each place, it is possible that there is a coin and / or a lever. Whenever we pass a place with a coin, we collect the coin, and no other coin appears in the same place if we return to it later. Whenever we pass through a location with a lever, we push the lever, and we never have to re-start it. Each lever opens a set of paths that connect pairs of neutral locations. Some paths are already open initially. To cross each path, we must defeat (or capture, if we want to become masters) the monsters that appear on this path. Monsters always appear when crossing any path, so it is always necessary to defeat them, even if they pass through a path that we have crossed before. To defeat a monster, we use the monsters we have already captured. Our monsters have a list of M attacks, each with a mana cost and a damage value that is imposed to the target monster. We are at location 1 and the exit of the map is at location V. Location 1 does not contain a coin or a lever.
Since this is a serious game and it has to be taken seriously, João Henrique, who became a fan of graph theory after studying the course given by Teacher Claus, is trying to optimize our crossing. He asked for his help to calculate the minimum cost (mana) needed to cross, collect all the coins and ... not catching any monster (Jonny, do you think the balloon is spherical and frictionless? How do you want to become a master monster captor, João Henrique?).
The input is composed of several test cases and ends with end of file (EOF). The first line of a test case contains the integers M, V, E, C, and L. Each of the next M lines describes an attack. Each line is composed of integers v and w, which are respectively the damage caused by the attack and the mana cost of the attack. Each of the next E lines describes a path. Each line starts with four integers a, b, m, and l. The path connects places a and b. The next m integers are the hit points h of each of the m monsters that appear on the way. If the integer l is zero, then the path is initially open. Otherwise, it is released by the label lever 1. There is at most one path connecting a couple of locations. Each of the next C lines describes a coin. For 1 ≤ i ≤ C, the i-th line contains an integer u, the label of the vertex in which is the label currency i. Each of the next L lines describes a lever. For 1 ≤ i ≤ L, the i-th line contains an integer u, the label of the vertex in which the label lever i is.
Restrictions:
1 ≤ M, v, w, h ≤ 100, 0 ≤ m ≤ 20;
1 ≤ V ≤ 100, 0 ≤ E ≤ V (V – 1) / 2, 1 ≤ a, b, u ≤ V
0 ≤ C, L ≤ 5, 0 ≤ l ≤ L
For each test case, print a single line with the response.
| Input Sample | Output Sample |
|
1 1 0 0 0 1 1 2 4 4 2 2 9 2 2 1 1 2 1 0 10 1 3 0 2 1 4 3 1 2 11 1 3 4 1 0 100 4 2 3 2 |
0 11 |