Problem C
Circuit Game

You’ve just found a most curious electro-mechanical game in a dusty corner of the saloon. No one seems to know where it came from, but the instructions promise riches to those who are able to play it well.

The operation of the machine is as follows. First, you insert some coins into the machine. Then, you flip some of the switches on the front of the machine. Each switch is initially in the ON position, and to switch it to the OFF position, you must pay a price. The total cost of all switches you put in the OFF position must be at most the value of the coins you inserted. When you’re happy with your selection of switches, you hit the big red button. Then, the game runs a series of test cases against your selection of switches. Each time you pass a test, you will receive the reward amount associated with that test. However, as soon as you fail even a single test, the game halts and does not process any further tests. You would like to maximize the amount of profit you make from a single round of the game, given that you can spend at most C coins.

Internally, the machine works as follows. There are $N$ terminals, numbered 1 through $N$, and a battery which spans terminals 1 and 2. Terminals may be joined by switches, each of which connects (in the ON position) or doesn’t connect (in the OFF position) two distinct terminals. We say that there is power across two terminals $a$ and $b$ if there is a path between $a$ and $1$ and a path between $b$ and $2$ (or between $a$ and $2$ and between $b$ and $1$). Note that such a path can only go through switches which are in the ON position. You will pass a test case if there is not any power across the two terminals associated with the test.

By the way, you should ensure that the battery is not short-circuited (i.e., there should not be a path from terminal 1 to 2), or else the entire machine will probably explode, taking you and your rewards with it.

Input

The first line contains 4 integers, $C$, $N$, $M$, and $T$, where $2\le N$, $1\le C, M, T$ and $C, N, M, T\le 1000$. The next $M$ lines each contain 3 integers $u$, $v$, and $c$, indicating that there is a switch between terminals $u$ and $v$ with cost $c$ ($1\le u<v\le N$, $0\le c\le 1000$). The next $T$ lines each contain 3 integers $u$, $v$, and $r$, indicating that there is a test case which tests terminals $u$ and $v$ with a reward of $r$ ($1\le u<v\le N$, $0\le r\le 1000$). There is at most one switch and one test case for a given pair of terminals.

Output

Output the largest possible profit you can obtain, i.e., the total reward minus the total number of coins you used, for a single play of the game. If there is no way to prevent a short circuit or no way to make positive amount of profit, output “The only winning move is not to play.”

3 4 3 2
2 4 2
1 3 3
3 4 1
2 3 10
1 4 100

7

20 5 5 3
4 5 4
3 4 9
1 5 8
1 3 4
2 3 3
2 4 3
3 5 8
4 5 7

6

1 3 2 1
1 2 1
2 3 0
1 3 1

The only winning move is not to play.