TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2507
  • 题目
  • P2507河城荷取
    限制 : 时间限制 : 10000 MS   空间限制 : 128000 KB
    问题描述

    在幻想乡,河城荷取是擅长高科技工业的河童。荷取的得意之作除了光学迷彩外,还有震动整个幻想乡的巨型人形『非想天则』。不过由于人形太过巨大,所以为它充能是一件很麻烦的事。人形一共有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 

    样例输出


    提示

    对于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)都只出现一次


    来源  东方幻想乡系列模拟赛 Stage 4