30019 - Job Hunt

时间限制 1 秒 内存限制 128 MB

题目描述

奶牛们正在找工作。农场主约翰知道后，鼓励奶牛们四处碰碰运气。而且他还加了一条要求：一头牛在一个城市最多只能赚 $D\ (1 \le D \le 1000)$ 美元，然后它必须到另一座城市工作。当然，它可以在别处工作一阵子后又回到原来的城市再最多赚 $D$ 美元。而且这样的往返次数没有限制。

城市间有 $P\ (1 \le P \le 150)$ 条单向路径连接，共有 $C\ (1 \le C \le 220)$ 座城市，编号从 $1$ 到 $C$ 。奶牛贝茜当前处在城市 $S\ (1 \le S \le C)$ 。路径 $i$ 从城市 $A_i$ 到城市 $B_i$ （ $1 \le A_i,B_i \le C$ ），在路径上行走不用任何花费。

为了帮助贝茜，约翰让它使用他的私人飞机服务。这项服务有 $F\ (1 \le F \le 350)$ 条单向航线，每条航线是从城市 $J_i$ 飞到另一座城市 $K_i$ （ $1 \le J_i,K_i \le C$ ），费用是 $T_i\ (1 \le T_i \le 50000)$ 美元。如果贝茜手中没有现钱，可以用以后赚的钱来付机票钱。

贝茜可以选择在任何时候，在任何城市退休。如果在工作时间上不做限制，贝茜总共可以赚多少钱呢？如果赚的钱也不会出现限制，就输出 $-1$ 。

输入

第一行： $5$ 个用空格分开的整数 $D$ ， $P$ ， $C$ ， $F$ ， $S$ 。

第 $2$ 到第 $P+1$ 行：第 $i+1$ 行包含 $2$ 个用空格分开的整数，表示一条从城市 $A_i$ 到城市 $B_i$ 的单向路径。

接下来 $F$ 行，每行 $3$ 个用空格分开的整数，表示一条从城市 $J_i$ 到城市 $K_i$ 的单向航线，费用是 $T_i$ 。

输出

一个整数，在上述规则下最多可以赚到的钱数。

样例

样例 1

输入

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

输出

提示

这个世界上有五个城市，三条单向路径和两条单向航线。贝茜从一号城市开始她的旅行，她在离开一个城市前最多只能在这个城市赚 $100$ 美元。

贝茜可以通过从一号城市 $\to$ 五号城市 $\to$ 二号城市 $\to$ 三号城市的旅行赚到 $4 \times 100 - 150 = 250$ 美元。

（注：在四个城市各赚 $100$ 美元，从五号城市飞到二号城市花掉 $150$ 美元）

来源：USACO2009 十一月银组