TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2507
  • Problem
  • P2507河城荷取
    Limits : Time Limit : 10000 MS   Memory Limit : 128000 KB
    Description

    在幻想乡,河城荷取是擅长高科技工业的河童。荷取的得意之作除了光学迷彩外,还有震动整个幻想乡的巨型人形『非想天则』。不过由于人形太过巨大,所以为它充能是一件很麻烦的事。人形一共有N个电能池,编号1..N。其中前L个电能池(即编号为1..L的电能池)连接着外部充能接口,而编号为N的电能池连接着动力炉核心。在N个蓄能池之间有M条单向管道,每条管道有一个激活代价cost和电能传输极限limit。当激活度达到某个值时,所以激活代价小于等于这个值的管道都会被激活,但是每一条管道只能够最多传送limit个单位的电能。外部接口到电能池和电能池到动力炉核心的管道传输没有限制并且激活代价为0。现在荷取想往动力炉核心输入至少K个单位的电能,求需要的最小激活度。

    Input Format

    第1行:4个正整数N,M,L, K
    第2..M+1行:4个整数,u,v,limit,cost,表示一条由u到v的管道,传输极限limit,激活代价为cost

    Output Format

    第1行:1个整数,表示最小激活代价

    Sample Input

    6 5 3 3 
    1 4 2 4 
    2 4 3 5 
    3 5 4 2 
    4 6 2 3 
    5 6 3 4 

    Sample Output


    Hint

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


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