题目描述

奶牛们没钱了，正在找工作。农夫约翰知道后，希望奶牛们四处转转，碰碰运气。而且他还加了一条要求：一头牛在一个城市最多只能赚 $d$ 美元，然后它必须到另一座城市工作。当然，它可以在别处工作一阵后又回来原来的城市再最多赚 $d$ 美元。而且这样往往返返的次数没有限制。城市间有 $p$ 条单向路径连接，共有 $c$ 座城市，编号 $1 \ldots c$。贝希当前处在城市 $s$。路径 $i$ 从城市 $a_i$ 到城市 $b_i$，在路径上行走不用花任何费用。为了帮助贝希，约翰让它使用他的私人飞机服务。这项服务有 $f$ 条航线，每条航线是从城市 $j_i$ 飞到另一座城市 $k_i$，费用是 $t_i$ 美元。如果贝希手中如果没有现钱，可以用以后赚的钱来付机票钱。贝希可以选择任何时候，在任何城市退休。如果在工作时间上不作限制，贝希总共可以赚多少钱呢？如果赚的钱也不会出现限制，就输出 -1。

输入格式

第一行：$5$ 个空格分开的整数 $d, p, c, f, s$。

第二行到第 $p+1$ 行：第 $i+1$ 行包含 $2$ 个空格分开的整数，表示一条从 $a_i$ 到 $b_i$ 的单向路径。

第 $p+2$ 行到第 $p+f+1$ 行：第 $p+i$ 包含 $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

250

样例说明 1

贝希可以从城市 $1$ 到 $5$ 再到 $2$，最后到 $3$，总共赚 $4\times100 - 150 = 250$ 美元。

数据规模与约定

对于 $100\%$ 的数据，$1 \leq d \leq 10^3$，$1 \leq p \leq 150$，$2 \leq c \leq 220$，$1 \leq s \leq c$，$1 \leq f \leq 350$，$1 \leq j_i, k_i, a_i, b_i \leq c$，$1 \leq t_i \leq 5\times10^4$。

题目来源

Silver