奶牛们正在找工作。农场主约翰知道后，鼓励奶牛们四处碰碰运气。而且他还加了一条要求：一头牛在一个城市最多只能赚 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。

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

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

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

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

来源：USACO2009 十一月银组