版权声明

本题由 搬运，版权归 AtCoder 所有。

题目来源：https://atcoder.jp/contests/agc018/tasks/agc018_c

本题与题目来源处的题目不尽相同。

注意

本题有加强版：

题目描述

你想要雇佣一些人来做三项工作，其中第 $i$ 项工作需要恰好 $p_i$ 个人。

有 $p_1 + p_2 + p_3$ 个人参加工作，第 $i$ 个人做第 $j$ 项工作需要 $a_{j, i}$ 元工资，且每个人只能做一项工作。

那么你至少需要花多少元才能完成雇佣？

输入格式

本题有多组数据。

对于每组数据：

第一行三个正整数 $p_1, p_2, p_3\ (1 \le p_i \le 1000)$。

下面一个 $3 \times (p_1 + p_2 + p_3)$ 的正整数矩阵 $\{a_{3, p_1 + p_2 + p_3}\}\ (1 \le a_{i, j} \le 10^9)$。

输入以 EOF 结束。

保证单个测试点内所有 $(p_1 + p_2 + p_3)^2$ 的和不大于 $10^7$，且输入的数字个数不超过 $2.5 \times 10^5$。

输出格式

对于每组数据，输出一行一个正整数表示答案。

样例

2 3 2
8 5 4 6 2 7 3
2 9 3 4 6 1 8
6 1 7 8 5 9 4
2 3 2
1 2 3 1 2 3 1
4 5 6 4 5 6 4
7 8 9 7 8 9 7
4 5 6
1 1 1 1 2 1 1 1 1 2 1 1 1 1 2
1 1 2 1 1 2 1 1 2 1 1 2 1 1 2
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
7 5 3
9 12 9 7 7 12 10 8 6 9 12 9 12 14 16
11 11 7 10 11 9 11 11 11 5 6 6 8 8 6
5 9 11 11 15 12 9 9 14 9 10 7 6 12 9

18
34
21
110