Time Limit:1000ms Memory Limit:65536KB

Description

    zsasuke平时没事的时候也喜欢去不高山,这时候都是别人值班.可是每次zsasuke想搭车的时候,
车上位置都有限,而司机按女士优先的原则让mm先上,每次轮到zsasuke的时候,已经没位置了,所以
zsasuke搭车基本每次都失败.终于,zsasuke决定乱搞了----出高价,别人出1元,他出3元,结果,
经过了n+1次搭车失败后,zsasuke终于搭上了一次车.结果,其他男生也纷纷效仿....经过了n个
月以后,搭车的男生已经很少有人愿意才出1元了.所以,司机的搭车计划也要跟着改变,才能获得最大利益.

Input

多case,每个case,第一行,3个数,K,N,C(1<=K<=3000,2<=N<=1000,1<=C<=30)N,C的描述见上题
接下来K行,每行4个数,a,b,f,d代表有d个旅客想从a景点到b景点,而且,他们每个人愿意出f元.
(a和b在1到N之间,并且a!=b,1<=d<=C,1<=f<=100)

Output

对每个test case输出一行,表示最多可以赚多少钱.

Sample Input

3 2 1
1 2 5 2
1 2 1 1
2 1 2 1

Sample Output

7

Hint

从1到2搭一人,收5元,从2到1搭一人,收2元,共7元.

Author

zsasuke

Source