5546: BZOJ1546:uva4409 - Ironman Race in Treeland
Memory Limit:64 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
河蟹国的道路特别有特点,每一条道路上都有许多景点供游客观赏,同时每条路要经过都要付一定的钱。而河蟹国的特点就是任意两个城市之间有切仅有一条简单路径,这样使游客旅行方便了许多。 XL准备在河蟹市进行一次旅行,他可以从任意一个城市出发,经过不重复的一些路径之后结束他的旅程。但是他带的钱有限,所以他希望知道在最好情况下自己最多能够得到多少欢乐值。 当然,这个欢乐值可能为0——没有任何一个他喜欢并且可以去的景点,所以他就世界回家看仙剑3去了。
输入格式
第一行三个整数N M K,分别表示河蟹国的城市数,道路数和XL身上所带的钱的数量。 接着有M行,每行4个整数Ai Bi COSTi VALi,分别表示第i-1条路径连接着Ai,Bi两个城市,经过它需要付COSTi元钱并且得到VALi的欢乐值。 N≤30000,M≤30000*30000,K≤10^9 0≤COSTi≤1000;0≤VALi≤1000
输出格式
输出文件仅一行一个整数,表示XL在最好的情况下能够得到的欢乐值是多少。
样例输入
4 3 2 1 2 1 1 1 3 1 2 1 4 2 3
样例输出
3
提示
ACM/ICPC 2008吉隆坡赛区
题目来源
鸣谢刘汝佳先生授权使用