题目描述

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

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

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

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

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

输入格式

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

第${2..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 }$到 ${5 }$再到 ${2 ，}$最后到 ${3, }$总共赚 ${4\times 100 - 150 = 250 }$美元。