#P5425. Honor

    ID: 4440 传统题 1000ms 128MiB 尝试: 58 已通过: 7 难度: 7 上传者: 标签>CF2300提高+/省选-阈值二值化最小割建模Dinic当前弧优化最大流最小割定理

Honor

Description

小K和同学们期待已久的暑假即将到来。然而小K的班主任兼德育处主任却莫名失踪了一个月。据小道消息,他在高 考后才会出现。但现在德育处有诸多繁杂的工作,确定每个班的"三好学生"便是最令人头痛的。HY中学的大Boss圆 规要求N个班的班主任按照学生的综合素质推荐学生。但他深深地知道,每个班主任都会无一例外地使用xls把M名 学生数次月考成绩相加排序,然后从高到底依次录取。圆规知道每个班学生成绩的排序和每个学生得到该荣誉的" 负"能量Aij。显然,"负"能量也是有正有负的。他不希望有些学生拿到"三好学生"后依然肆无忌惮地拔掉教室里监 控的探头,或是在晚餐时间在篮球场上尽情玩耍(这在HY中学是会被通报批评的)。他希望能够多发扬正能量。圆规 从不在乎"三好学生"的数量,但是他却不得不考虑学生的感受。学生在学生会上

(1)提出了K条无理的要求,每条要求对于班级u、v,要求班级u的三好学生数量Su和班级v三好学生数量Sv, 满足Su-Sv<=w。

(2)提出每个班至少一张奖状。

鉴于HY中学的高一高二学生在5月下旬某一个酷热的晚上,忍无可忍围起了整栋教学楼,并且齐声高声叫喊:"开空 调!"但学校善后处理十分不得力。

圆规决定全盘接受学生的建议,以平息学生的怒气。但是,他还是想知道最小的负能量。

Format

Input

第1行 为三个数N、M、K如题意所示。

第2-N+1行,每行M个数,表示按成绩从高到底排序的每个学生的"负"能量大小。

第N+2-N+K+1行,每行三个数u、v、w如题意所示。

本站评测数据满足 1≤N≤9001\le N\le900,1≤M≤601\le M\le60,0≤K≤200000\le K\le20000,1≤u,v≤N1\le u,v\le N,∣Aij∣<1000|A_{ij}|<1000,0≤w≤10000\le w\le1000。每班至少选一人且至多选本班人数。每班恰选一人是一组可行方案。

Output

最小的负能量。

Samples

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