uva4409 - Ironman Race in Treeland

河蟹国的道路特别有特点，每一条道路上都有许多景点供游客观赏，同时每条路要经过都要付一定的钱。而河蟹国的特点就是任意两个城市之间有且仅有一条简单路径，这样使游客旅行方便了许多。

XL 准备在河蟹国进行一次旅行，他可以从任意一个城市出发，经过不重复的一些路径之后结束他的旅程。但是他带的钱有限，所以他希望知道在最好情况下自己最多能够得到多少欢乐值。

当然，这个欢乐值可能为 $0$——没有任何一个他喜欢并且可以去的景点，所以他就回家看仙剑 $3$ 去了。

输入格式

第一行三个整数 $N, M, K$，分别表示河蟹国的城市数、道路数和 XL 身上所带的钱的数量。

接着有 $M$ 行，每行 $4$ 个整数 $A_i, B_i, \mathrm{COST}_i, \mathrm{VAL}_i$，表示第 $i$ 条路径连接着 $A_i, B_i$ 两个城市，经过它需要付 $\mathrm{COST}_i$ 元钱并且得到 $\mathrm{VAL}_i$ 的欢乐值。

输出格式

输出仅一行一个整数，表示 XL 在最好的情况下能够得到的欢乐值是多少。

样例输入

4 3 2
1 2 1 1
1 3 1 2
1 4 2 3

样例输出

3

样例解释

带的钱数为 $2$。走 $2\to 1\to 3$ 这条路径，花费 $1+1=2$ 元，欢乐值为 $1+2=3$；直接走 $1\to 4$ 也花费 $2$ 元，欢乐值为 $3$。两者都达到最大值 $3$。

数据范围

• $N\le 3\times 10^4$，且题目保证任意两个城市之间有且仅有一条简单路径（即道路构成一棵树）；
• $K\le 10^9$；
• $0\le \mathrm{COST}_i\le 1000$，$0\le \mathrm{VAL}_i\le 1000$。

来源与许可

本题为 ACM/ICPC 2008 吉隆坡赛区试题「Ironman Race in Treeland」，题面与测试数据整理自 BZOJ 1546。

样例 1

输入

4 3 2
1 2 1 1
1 3 1 2
1 4 2 3

输出

3