2705: 河城荷取
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
在幻想乡，河城荷取是擅长高科技工业的河童。荷取的得意之作除了光学迷彩外，还有震动整个幻想乡
的巨型人形『非想天则』。不过由于人形太过巨大，所以为它充能是一件很麻烦的事。人形一共有N个电能池，编号1..N。其中前L个电能池(即编号为1..L的电能池)连接着外部充能接口，而编号为N的电能池连接着动力炉核心。在N个蓄能池之间有M条单向管道，每条管道有一个激活代价cost和电能传输极限limit。当激活度达到某个值时，所以激活代价小于等于这个值的管道都会被激活，但是每一条管道只能够最多传送limit个单位的电能。外部接口到电能池和电能池到动力炉核心的管道传输没有限制并且激活代价为0。现在荷取想往动力炉核心输入至少K个单位的电能，求需要的最小激活度。
输入
第1行：4个正整数N,M,L, K
第2..M+1行：4个整数，u,v,limit,cost，表示一条由u到v的管道，传输极限limit，激活代价为cost
输出
第1行：1个整数，表示最小激活代价
样例输入 复制
6 5 3 3
1 4 2 4
2 4 3 5
3 5 4 2
4 6 2 3
5 6 3 4样例输出 复制
4提示
当激活度为4时，除了(2,4)外其他管道都能够使用。此时能够输入恰好4个单位电能。具体如下：
(1,4)输送2个单位电力
(4,6)输送2个单位电力
(3,5)输送2个单位电力
(5,6)输送2个单位电力
对于30%的数据：1 ≤L≤N ≤100，0 ≤ M ≤2,000，1 ≤cost≤10,000
对于60%的数据：1 ≤L≤N ≤1,000，0 ≤ M ≤20,000，1 ≤cost≤10,000
对于100%的数据：1 ≤L≤N ≤2,000，0 ≤ M ≤80,000，1 ≤cost≤1,000,000
对于100%的数据：1 ≤limit≤1,000
保证任意(u,v)都只出现一次。