[AHOI2012] 收集资源

题目描述

![](https://cdn.luogu.com.cn/upload/pic/1637.png) ![](https://cdn.luogu.com.cn/upload/pic/1638.png)

输入输出格式

输入格式


![](https://cdn.luogu.com.cn/upload/pic/1639.png)

输出格式


![](https://cdn.luogu.com.cn/upload/pic/1640.png)

输入输出样例

输入样例 #1

8 8 10
1 1 3
2 2 4
3 3 5
3 4 3
4 3 2
4 4 6
5 5 7
6 6 8

输出样例 #1

28

说明

数据: 50%: 1<=N,M,T<=100 100%: 1<=N,M,T<=200