题目描述

奶牛们没钱了，正在找工作。农夫约翰知道后，希望奶牛们四处转转，碰碰运气。而且他还加了一条要求：一头牛在一个城市最多只能赚$\red{D(1 <= D <= 1,000)}$美元，然后它必须到另一座城市工作。

当然，它可以在别处工作一阵后又回来原来的城市再最多赚$\red{D}$美元。而且这样往往返返的次数没有限制。

城市间有$\red{P (1 <= P <= 150)}$条单向路径连接，共有$\red{C(2 <= C <= 220)}$座城市，编号$\red{1..C. }$贝希当前处在城市$\red{S (1 <= S <= C)}$。路径 $\red{i }$从城市$\red{A_i }$到城市$\red{B_i (1 <= A_i <= C}$; $\red{1 <= B_i <= C)，}$在路径上行走不用花任何费用。

为了帮助贝希，约翰让它使用他的私人飞机服务。这项服务有$\red{F}$条$\red{(1 <= F <= 350)}$航线，每条航线是从城市$\red{J_i}$飞到另一座城市$\red{K_i (1 <=J_i <= C}$; $\red{1 <= K_i <= C)，}$费 用是$\red{T_i (1 <= T_i <= 50,000)}$美元。

如果贝希手中如果没有现钱，可以用以后赚的钱来付机票钱。贝希可以选择任何时候，在任何城市退休。如果在工作时间上不作限制，贝希总共可以赚多少钱呢？ 如果赚的钱也不会出现限制，就输出$\red{-1}$。

输入格式

第$\red{1}$行: $\red{5}$个空格分开的整数 $\red{D, P, C, F, S}$

第$\red{2..P+1}$行: 第 $\red{i+1}$行包含$\red{2}$个空格分开的整数，表示一条从$\red{A_i }$到 $\red{B_i}$的单向路径

第$\red{P+2..P+F+1}$行: 第$\red{P+i }$包含$\red{3}$个空格分开的整数，表示一条从$\red{J_i}$到$\red{K_i}$的单向航线，费用为$\red{T_i}$

输出格式

第$\red{1}$行: 在上述规则下的最多可赚的钱数。

样例

输入样例

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

输出样例

250

提示

样例说明：贝希可以从城市 $\red{1 }$到 $\red{5 }$再到 $\red{2 ，}$最后到 $\red{3, }$总共赚 $\red{4\times 100 - 150 = 250 }$美元。