2607: 钻石交易

萌萌和南南在今年寒假出去愉快地旅游，他们选择了n座城市作为旅游计划的候选城市，
城市用正整数1到n编号。萌萌和南南从编号为s的城市出发，出发时萌萌带着m颗巨大
的钻石，他准备在旅途的过程中将这些钻石中的一部分卖掉，赚取一些钱给南南买一枚戒
指。
萌萌开始时有k元钱，n座城市之间通过t条单向道路连接，通过特定的道路需要付出一
定数量的钱，注意萌萌身上剩的钱必须足够才能通过这条道路。在途径的任意一个城市
（包括起点和终点），萌萌可以选择剩下钻石中的任意一些卖掉，每个城市每颗戒指的卖出
价可能是不相同的。
给出道路的信息和每个城市每颗钻石的卖出价，萌萌可以选择在任何一个城市结束旅行，
问萌萌最后身上最多能剩余多少钱？

第一行包含五个正整数n,t,m,k,s。
接下来n 行，每行包含m 个不超过10000的非负整数，依次对应每个城市每颗钻石的卖
价，即第i行第j个数表示第j颗钻石在编号为i的城市的卖价。
接下来t行，每行包含三个非负整数，᧿述一条单向道路，表示从编号为i的城市到编号
为j的城市有一条通过代价为c的道路。

仅包含一个正整数，表示萌萌最后身上最多能剩余的钱数。

4 5 2 7 1
0 0
10 0
0 8
100 10
1 2 5
1 3 10
1 4 8
2 3 4
2 4 6

16