旅行
题目描述
乐乐要开始他的背包旅行，这次共n个城市，编号为1~n。 乐乐从编号为1的城市出发，前往编号为n的城市。每个城市都有一件物品，重量为wi，价值为vi。乐乐从一个城市到另一个城市，如果背包中的物品重量为a，行走距离为b时，花费的体力为a*b,乐乐最多只能背总重量为W的物品。乐乐希望到达n时，背包中的物品价值最大，同时花费的体力最小。n个城市之间共m条单向路，且无环，从一个城市出发之后，无法再回到这个城市。
输入数据
第一行3个整数n,m,W.
接下来 n 行，每行2个整数表示wi和vi
接下来 m 行，每行3个整数 xi,yi,zi 无重边，无自环。数据保证1可以到达n.
输出数据
输出两个整数，表示最大值价值和获得最大值情况下最小的体力消耗。
样例
5 6 10
2 2
1 3
3 5
4 2
2 3
1 2 1
2 4 5
2 5 3
1 3 4
3 4 2
4 5 2
10 20
提示
