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

#5425. Honor