IX Olimpiada Informatyczna 2001/2002
Author: Marcin Sawicki
|II stage contest|
In Byte Mountains there is a ski resort Bytegary. It is famous for its cross-country ski tracks. They are very picturesque because a part of them lies high in the mountains or in places hard to reach. Users of the tracks often make use of ski lifts that help reach some of the tracks. Each lift and each track starts and ends on a particular clearing. The ski tracks must not cross but they may run through natural rock tunnels or bridges.
The ski tracks may be one-way or two-way. Similarly, some ski lifts may be one- or two-way.
Using a ski lift is charged by means of magnetic cards. The cards can be bought at cash desks. Each card contains a particular number of points. Using each ski lift is connected with loosing some number of points, depending on the lift. Unfortunately, the cash desks do not refund unused points.
Today is the last day Byteoni is skiing. He has one card with some number of points left which he wants to use maximally. You may assume that the number of points is enough to return to Bytegary.
In the second line there is one positive integer k, 1 <= k <= 5000, equal to the total number of all ski tracks. Each of the successive k lines contains two distinct positive integers, separated by a single space, 1 <= p1 <> p2 < n. Those figures denote the numbers of the starting and the ending clearings of the given ski track. Two-way tracks are counted twice, and are represented in the input file by two (not necessarily consecutive) lines (of the form "p1 p2" and "p2 p1").
In the line number k+3 there is one positive integer m, 1 <= m <= 300, equal to the number of all the ski lifts. In the successive m lines the lifts are described. In each of those lines three positive integers q1, q2 and r are written; they are separated by single spaces. The numbers q1 and q2 denote the numbers of the clearings the lift starts and ends, respectively, 1 <= q1 <> q2 <= n. The number r equals the number of points that is charged for the lift ride, 1 <= r <= 1000. Two-way ski lifts are counted twice, and are represented in the input file by two (not necessarily consecutive) lines (of the form "q1 q2 r1" and "q2 q1 r2"). The price for the ski lift ride in one direction may differ from the price for the ride in the other direction.
In the last line there are two positive integers b and s, separated by a single space 1 <= b <= n, 1 <= s <= 2000. The former is the number of the clearing Byteoni is present on, and the latter equals the number of points on his last magnetic card.
5 2 6 3 2 3 5 1 5 3 4 1 2 4 3 4 3 1 1 4 3 5 5 2 2 3 4 5 4 9the correct answer is in the following output file kur.out: