Bessie's Job Hopping

Bessie is in a financial pinch and must work in various cities to earn money, but Farmer John has imposed a rule: in any city Bessie can earn at most \(D\) dollars before she is forced to work somewhere else. However, Bessie is allowed to return to a city later and earn another \(D\) dollars. There is no limit on the number of times she can do this.

Bessie's world is represented as a directed graph with \(C\) cities (numbered from 1 to \(C\)) and two kinds of edges:

• Roads: There are \(P\) one-way roads. Traveling a road costs nothing, and upon arriving to the destination city she earns \(D\) dollars.
• Flights: There are \(F\) one-way flights. Each flight goes from city \(J_i\) to city \(K_i\) and costs \(T_i\) dollars. When Bessie takes a flight, her net gain is \(D - T_i\) dollars after working in the destination city. Bessie is allowed to pay for the flight even if she does not currently have the money; she can use money earned later.

Bessie starts in city \(S\) and may retire at any time. The task is to calculate the maximum amount of money Bessie can earn. If she can earn an arbitrarily large amount because of a cycle with a positive net gain, output -1.

Note: All formulas are in \(\LaTeX\) format.

inputFormat

The input consists of several space‐separated integers. The first line contains five integers: \(D\) \(C\) \(P\) \(F\) \(S\), where

• \(D\) (\(1 \leq D \leq 1000\)) is the maximum dollars Bessie can earn in a single city visit,
• \(C\) (\(2 \leq C \leq 220\)) is the number of cities,
• \(P\) (\(1 \leq P \leq 150\)) is the number of one-way roads,
• \(F\) (\(1 \leq F \leq 350\)) is the number of flights,
• \(S\) (\(1 \leq S \leq C\)) is the starting city.

Following this, there are \(P\) lines (or groups of 2 integers) each containing two integers \(A_i\) and \(B_i\) (\(1 \leq A_i, B_i \leq C\)), representing a one-way road from city \(A_i\) to city \(B_i\). Next, there are \(F\) lines (or groups of 3 integers) each containing \(J_i\), \(K_i\), and \(T_i\) (with \(1 \leq J_i, K_i \leq C\) and \(1 \leq T_i \leq 50000\)), representing a flight from city \(J_i\) to city \(K_i\) with a cost \(T_i\) dollars.

You may assume that all integers are separated by whitespace.

outputFormat

Output a single integer, which is the maximum amount of money Bessie can earn. If Bessie can earn an arbitrarily large amount (due to a profitable cycle), output -1.

sample

5 4 4 1 1
1 2
2 3
3 4
2 4
4 1 3

-1