题目描述

奶牛们正在找工作。农场主约翰知道后，鼓励奶牛们四处碰碰运气。而且他还加了一条要求：一头牛在一个城市最多只能赚D（1≤D≤1000）美元，然后它必须到另一座城市工作。当然，它可以在别处工作一阵子后又回到原来的城市再最多赚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≤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 3 5 2 1
1 5
2 3
1 4
5 2 150
2 5 120

250

提示

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

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

(注:在四个城市各赚100美元,从五号城市飞到二号城市花掉150美元)