J13 习题-1 赚钱

题目描述

$\text{zzy}$ 现在决定环游中国，顺便赚点钱。$\text{zzy}$ 在一个城市最多只能赚 $D$ 元，然后他可以选择退休也就是停止赚钱，或者去其它城市工作。当然，他可以在别处工作一阵子后又回到原来的城市再赚 $D$ 元。这样的往返次数是没有任何限制的。

城市间有 $P$ 条单向路径连接，共有 $C$ 座城市，编号从 $1$ 到 $C$。路径 $i$ 从城市 $Ai$ 到城市 $Bi$，在路径行走上不用任何花费。

$\text{zzy}$ 还可以乘飞机从某个城市飞到另一个城市。共有 $F$ 条单向的航线，第 $i$ 条航线是从城市 $Ji$ 飞到另一座城市$Ki$ ，费用是 $Ti$ 元。假如 $\text{zzy}$ 身上没有现钱，他可以用以后赚的钱来付机票钱。

$\text{zzy}$ 可以从任何一个城市出发开始赚钱，并且选择在任何时候、任何城市退休。现在 $\text{zzy}$ 想要知道，如果在工作时间上不做限制，那么 $\text{zzy}$ 共可以赚多少钱呢？如果赚的钱也不会出现限制，那么就输出orz。

输入格式

第一行，$4$ 个用空格分开的正整数，$D,P,C,F$。

第二行到 $P+1$ 行，第 $i+1$ 行包含 $2$ 个用空格分开的整数，表示一条从城市 $Ai$ 到城市 $Bi$ 的单向路径。

接下来的 $F$ 行，每行 $3$ 个用空格分开的正整数，表示一条从城市 $Ji$ 到城市 $Ki$ 的单向航线，费用为 $Ti$。

输出格式

如果 $\text{zzy}$ 赚的钱没有限制，输出orz。如果有限制，那么就输出在给定的规则下 $\text{zzy}$ 最多可以赚到的钱数。

样例输入

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

样例输出

250

样例分析

如上所述。

数据范围

对于$100\%$的数据，$1\le D\le 1000,1\le P\le 200,2\le C\le 300,1\le F\le 400$。