题目描述

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

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

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

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

输入格式

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

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

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

输出格式

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

样例

输入样例

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

输出样例

6

提示

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

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

输入详细信息：

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