#5425. Honor

内存限制:128 MiB 时间限制:10 Sec

题目描述

小K和同学们期待已久的暑假即将到来。然而小K的班主任兼德育处主任却莫名失踪了一个月。据小道消息,他在高
考后才会出现。但现在德育处有诸多繁杂的工作,确定每个班的"三好学生"便是最令人头痛的。HY中学的大Boss圆
规要求N个班的班主任按照学生的综合素质推荐学生。但他深深地知道,每个班主任都会无一例外地使用xls把M名
学生数次月考成绩相加排序,然后从高到底依次录取。圆规知道每个班学生成绩的排序和每个学生得到该荣誉的"
负"能量Aij。显然,"负"能量也是有正有负的。他不希望有些学生拿到"三好学生"后依然肆无忌惮地拔掉教室里监
控的探头,或是在晚餐时间在篮球场上尽情玩耍(这在HY中学是会被通报批评的)。他希望能够多发扬正能量。圆规
从不在乎"三好学生"的数量,但是他却不得不考虑学生的感受。学生在学生会上
(1)提出了K条无理的要求,每条要求对于班级u、v,要求班级u的三好学生数量Su和班级v三好学生数量Sv,
      满足Su-Sv<=w。
(2)提出每个班至少一张奖状。
鉴于HY中学的高一高二学生在5月下旬某一个酷热的晚上,忍无可忍围起了整栋教学楼,并且齐声高声叫喊:"开空
调!"但学校善后处理十分不得力。圆规决定全盘接受学生的建议,以平息学生的怒气。但是,他还是想知道最小
的负能量。

输入格式

第1行 为三个数N、M、K如题意所示。
第2-N+1行,每行M个数,表示按成绩从高到底排序的每个学生的"负"能量大小。
第N+2-N+K+1行,每行三个数u、v、w如题意所示。
n<=120,m<=60,K<=20000,Aij的绝对值小于1000,w<=1000。

输出格式

最小的负能量。

样例

样例输入


			
3 4 3
13 -4 -1 -2
1 -2 3 1
-3 4 2 1
2 3 0
3 2 0
1 2 1

样例输出


			
7

数据范围与提示