Job Hunt

Interview

Time limit1sMemory limit128 MB

Summary

Bessie earns at most D per city visit, travels free paths and paid flights, and can repeat cities; find the maximum total profit or -1 if unbounded.

Level: Medium7 of 10
Topics: Graph, Shortest path, Dynamic programming, Greedy
Solved: No attempts yet

Problem

Bessie is running out of money and is looking for work. Farmer John knows this and wants his cows to travel around, so he has made a rule: a cow can earn at most $D$ ( $1 \le D \le 1000$ ) dollars in a city before she must go work in another city. However, after working elsewhere for a while, Bessie may return to a city and again earn up to $D$ dollars there. There is no limit on how many times she can do this.

Bessie's world has $C$ ( $2 \le C \le 220$ ) cities, numbered $1$ through $C$ , connected by $P$ ( $1 \le P \le 150$ ) one-way paths. Bessie is currently in city $S$ ( $1 \le S \le C$ ). Path $i$ runs one-way from city $A_i$ to city $B_i$ ( $1 \le A_i \le C$ ; $1 \le B_i \le C$ ) and costs nothing to traverse.

To help Bessie, Farmer John gives her access to his private jet service. This service has $F$ ( $1 \le F \le 350$ ) routes; each route is a one-way flight from a city $J_i$ to another city $K_i$ ( $1 \le J_i \le C$ ; $1 \le K_i \le C$ ) that costs $T_i$ ( $1 \le T_i \le 50000$ ) dollars. Bessie may pay for tickets out of future earnings even if she has no cash on hand.

Bessie may retire whenever and wherever she likes. Given unlimited time, and assuming she earns the full $D$ dollars in every city she can reach, what is the most money she can make? Print $-1$ if there is no limit to this amount.

Input

Line 1: Five space-separated integers: $D$ , $P$ , $C$ , $F$ , and $S$ .
Next $P$ lines: line $i$ contains two space-separated integers $A_i$ and $B_i$ describing a one-way path from one city to another.
Next $F$ lines: each line contains three space-separated integers $J_i$ , $K_i$ , and $T_i$ describing a one-way jet flight from one city to another and its price.

Output

Line 1: A single integer, the most money Bessie can make while obeying the rule. Print $-1$ if there is no limit to this amount.

Hint

In this example the world has five cities, three paths, and two jet routes. Bessie starts in city $1$ , and she can earn only $100$ dollars in each city before moving on.

Bessie can travel city $1 \to$ city $5 \to$ city $2 \to$ city $3$ and make a total of $4 \times 100 - 150 = 250$ dollars.

Examples1

Example 1

Input

100 3 5 2 1
1 5
2 3
1 4
5 2 150
2 5 120

Expected output