[AdditionalFile5640.zip](file://AdditionalFile5640.zip?type=additional_file)

#5640. 「PA 2015 Final」Kurs tańca

标签: 传统 | 时间限制: 10000 ms | 内存限制: 256 MiB |

题目描述

题目译自 PA 2015 Final Kurs tańca

Bajtazar 正在规划舞蹈学校的课程安排。在新一届的交际舞课程中，学员们可以在没有舞伴的情况下报名，并提交与课程时段相关的偏好。对于 $t$ 个可选的课程时段，每位学员（包括女士和男士）都会声明：如果被分配到该时段，他们愿意支付多少费用。

Bajtazar 的任务是组建男女配对，并为每对舞伴分配一个他们学习舞蹈的时段，使得学校的总利润尽可能大。每位学员最多只能被分配到一个时段，且最多只能属于一对舞伴。由于舞厅足够大，因此每个时段可以容纳任意数量的舞伴对。

输入格式

输入的第一行包含三个整数 $n, m$ 和 $t$ $(1 \leq n, m \leq 10000, 1 \leq t \leq 10)$，分别表示报名参加课程的女士人数、男士人数以及可选的时段数量。女士的编号为 $1$ 到 $n$，男士的编号为 $n+1$ 到 $n+m$。

接下来的 $n+m$ 行中，第 $i$ 行包含一个由 $t$ 个整数组成的序列 $c_{i, 1}, c_{i, 2}, \ldots, c_{i, t}$ $(1 \leq c_{i, j} \leq 100000, j=1, 2, \ldots, t)$。数字 $c_{i, j}$ 表示第 $i$ 位学员如果被分配到第 $j$ 个时段所愿意支付的金额。

输出格式

在一行中输出一个整数，表示组织该舞蹈课程所能获得的最大利润。

样例

输入

2 3 2
5 1
5 1
1 1
2 2
3 4

输出

15

在其中一个最优解中，舞伴对 $(1, 4)$ 以及 $(2, 5)$ 都在时段 $1$ 跳舞。