Description

        Element TD is a hot game in the world of otaku, and all otakus are crazy about it. According to a CNN report, some friends even quarrel and fight because of the game. It is so terrible! To understand why this game drives people crazy, you decide to play the game now!

        Firstly, there are several maps in the game. Each map has a hole that monsters will come out from it unlimitedly. Monsters will only walk along the roads. Each road may contain up to a certain number of monsters. When a monster reaches a road junction, it will choose the next road to walk randomly.

 

 

        You have a castle to defend from monsters’ attack. To do so, you can build some towers at the road junctions to monitor the road and kill the intruding monsters. Different types of towers have different powers of killing (number of monsters that can be killed in a unit of time) and different building costs. The attack ranges of all the towers are unlimited. For example, for a tower with (power, cost) = (5, 10), then we need to pay 10 dollars to build the tower and this tower can kill 5 monsters in a unit of time.

        To be a perfect gamer, you must find the smallest cost for creating enough towers in a given map, such that you can block attacks from the monsters at any time.

Input

        The first line contains an integer t (t <= 20) that indicates the number of test cases.

        For each test case, the first line contains two integers n (2 <= n <= 70) and m (1 <= m <= n*(n-1)/2), denoting the number of intersections and the number of roads in this map, respectively. The intersections will be labeled by {1, 2, 3, …, n}.

        The next m lines are the information of the roads. Each line consists of three integers e_i, e_j, and cp(i, j). The integers ei and ej indicates that the road is from intersection i to intersection j, and the value cp(i, j) indicates that the road can contain at most cp(i, j) monsters. Each road is directed so that monsters can walk in one direction.

        The hole where monsters come out is located at intersection 1, and your castle is located at intersection n. The total number of monsters, which you will kill in a unit of time, will be less than 30,000.

        After the road information, the next line will be an integer Q (1 <= Q <= 100), indicating how many types of towers you can choose. And the following Q lines describe the information of each tower. Each line contains two integers p_i and g_i (1 <= p_i, g_i <= 1,000), which are the power and the cost of tower i, respectively. 

Output

        For each case, output a line with the minimum cost for creating enough towers.

Sample Input  Download

Sample Output  Download

Tags

Discuss