题目描述

为了表示不能输给人类，农场的奶牛们决定成立一家航空公司．她们计划每天早晨，从密歇根湖湖岸的最北端飞向最南端，晚上从最南端飞往最北端．

在旅途中，航空公司可以安 排飞机停在某些机场．他们需要你帮助来决定每天携带哪些旅客．沿着湖岸，有${N(1≤}$${N≤}$${10000)}$个由北至南编号为${1}$到${N}$的农场．

每个农场都有一个机场．这天，有${k(l≤}$${k≤}$${50000)}$群牛想要乘坐飞机旅行．每一群牛想要从一个农场飞往另一个农场．航班可以在某些农场停下带上部 分或全体的牛．奶牛们登机后会一直停留直至达到目的地

提供给你飞机的容量${C(1≤}$${C≤}$${100)，}$同时提供给你想要旅行的奶牛的信息，请你计算出这一天的航班最多能够满足几只奶牛的愿望．

输入格式

第${1}$行：${3}$个用空格隔开的整数${K，}$${N}$和${C.}$

第${2}$到${K+1}$行：

每一行有${3}$个用空格隔开的整数${S，}$${E，}$${M.}$表示有${M}$只奶牛想从农场${S}$乘飞机到农场${E}$．

输出格式

可以完成旅行的奶牛人数的最大值．

样例

输入样例

4 8 3
1 3 2
2 8 3
4 7 1
8 3 2

输出样例

6

提示

${3}$群想要旅行的奶牛，${8}$个农场，飞机上有${3}$个座位．

早晨，飞机把${2}$只牛从${1}$带到${3，}$${1}$只牛从${2}$带到${8，}$${1}$只牛从${4}$带到${7}$．晚上，航班把${2}$尺牛从${8}$带到${3}$．

输入详细信息：

四组奶牛，八个农场，三个座位飞机