奶牛们正在找工作。农场主约翰知道后，鼓励奶牛们四处碰碰运气。而且他还加了一条要求：一头牛在一个城市最多只能赚 $D(1 \le D \le 1000)$ 美元，然后它必须到另一座城市工作。当然，它可以在别处工作一阵子后又回到原来的城市再最多赚 $D$ 美元。而且这样的往返次数没有限制。

城市间有 $P(1 \le P \le 150)$ 条单向路径连接，共有 $C(2 \le C \le 220)$ 座城市，编号从 $1$ 到 $C$。奶牛贝茜当前处在城市 $S(1 \le S \le C)$。路径 $i$ 从城市 $A_i$ 到城市 $B_i(1≤A_i≤C,1≤B_i≤C)$，在路径上行走不用任何花费。

为了帮助贝茜，约翰让它使用他的私人飞机服务。这项服务有 $F$ 条 $(1 \le F \le 350)$ 单向航线，每条航线是从城市$J_i$飞到另一座城市$K_i(1 \le J_i \le C,1 \le K_i \le C)$，费用是 $T_i(1≤T_i≤50000)$ 美元。如果贝茜手中没有现钱，可以用以后赚的钱来付机票钱。

贝茜可以选择在任何时候，在任何城市退休。如果在工作时间上不做限制，贝茜总共可以赚多少钱呢？如果赚的钱也不会出现限制，就输出$-1$。

奶牛们正在找工作。农场主约翰知道后，鼓励奶牛们四处碰碰运气。而且他还加了一条要求：一头牛在一个城市最多只能赚 $D(1 \le D \le 1000)$ 美元，然后它必须到另一座城市工作。当然，它可以在别处工作一阵子后又回到原来的城市再最多赚 $D$ 美元。而且这样的往返次数没有限制。

城市间有 $P(1 \le P \le 150)$ 条单向路径连接，共有 $C(2 \le C \le 220)$ 座城市，编号从 $1$ 到 $C$。奶牛贝茜当前处在城市 $S(1 \le S \le C)$。路径 $i$ 从城市 $A_i$ 到城市 $B_i(1≤A_i≤C,1≤B_i≤C)$，在路径上行走不用任何花费。

为了帮助贝茜，约翰让它使用他的私人飞机服务。这项服务有 $F$ 条 $(1 \le F \le 350)$ 单向航线，每条航线是从城市$J_i$飞到另一座城市$K_i(1 \le J_i \le C,1 \le K_i \le C)$，费用是 $T_i(1≤T_i≤50000)$ 美元。如果贝茜手中没有现钱，可以用以后赚的钱来付机票钱。

贝茜可以选择在任何时候，在任何城市退休。如果在工作时间上不做限制，贝茜总共可以赚多少钱呢？如果赚的钱也不会出现限制，就输出$-1$。