Problem1592--VIJOS-P1399

1592: VIJOS-P1399

Time Limit: 0 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

Input

第一行4个整数n,m,t,v,分别是结点总数,通路总数,规定时间,及基德所拥有 的钱。接下去m行,每行4个整数a,b,c,d,a和b表示有通路的两结点,c为此路费 时,d代表此路过路费。 

Sample Input Copy

8 10 10 120
1 2 2 1
1 3 1 1
1 4 2 19
2 3 2 6
3 4 1 1
3 5 2 2
5 6 2 1
6 7 1 3
7 8 3 1
4 8 7 100

Sample Output Copy

9 119

HINT

2< =n< =100 1< =t,v< =500 样例说明 道路网如图所示【道路上括号外为费时,括号内为过路费】 [IMG]http://www.vijos.cn/upload/ProblemPic/P1XXX%20from%20%E7%8E%9B%E7%BB%B4-%E5%BD%B1%E4%B9%8B%E6%AD%8C.jpg[/IMG] 1-> 4-> 8即为所求路径,用时为9,费钱为119。