3649. [BZOJ 1458]士兵占领

【题目描述】

有一个 $M \times N$ 的棋盘，有的格子是障碍。

现在你要选择一些格子来放置一些士兵，一个格子里最多可以放置一个士兵，障碍格里不能放置士兵。

我们称这些士兵占领了整个棋盘当满足第 $i$ 行至少放置了 $Li$ 个士兵,第 $j$ 列至少放置了 $Cj$ 个士兵。

现在你的任务是要求使用最少个数的士兵来占领整个棋盘。

【输入格式】

第一行三个数 $M, N, K$ 分别表示棋盘的行数，列数以及障碍的个数。

第二行有 $M$ 个数表示 $Li$。

第三行有 $N$ 个数表示 $Ci$。

接下来有 $K$ 行，每行两个数 $X, Y$ 表示 $(X, Y)$ 这个格子是障碍。

【输出格式】

输出一个数表示最少需要使用的士兵个数。如果无论放置多少个士兵都没有办法占领整个棋盘，输出 $\text{JIONG!}$

【样例输入】

4 4 4
1 1 1 1
0 1 0 3
1 4
2 2
3 3
4 3

【样例输出】

4

【样例说明】

在此键入。

【数据规模与约定】

$M,N \le 100$,$0 \le K \le M \times N$

【来源】

BZOJ1458，洛谷P4311