Job Hunt

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.

• 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.

• 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.

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.