题目描述

译自 ROI Regional 2024 Day1 T3. Игра с таблицей

给定一个 $h$ 行 $w$ 列的表格 $A$，每个单元格中都有一个整数。行从上到下编号为 $1$ 到 $h$，列从左到右编号为 $1$ 到 $w$。

可以对这个表格进行以下操作：

• 选择一个列并删除它（左右两侧的列将变成相邻的）。
• 选择一个行并删除它（上下两侧的行将变成相邻的）。

这些操作可以任意次序、任意次数地进行。

确定是否可以通过这些操作使表格中所有数的和等于给定的数 $s$，如果可以，输出需要进行的操作及其顺序。

输入格式

第一行包含两个整数 $h$ 和 $w$ $(1 \leq h, w \leq 15)$，表示表格的行数和列数。

接下来的 $h$ 行中，每行包含 $w$ 个整数，表示表格 $A$ $(0 \leq A_{i,j} \leq 10^9)$。

最后一行包含一个整数 $s$ $(1 \leq s \leq 10^{18})$，表示所需的和。

输出格式

如果无法通过操作得到和为 $s$ 的表格，输出 NO。

否则：

• 第一行输出 YES。
• 第二行输出一个整数 $k$，表示需要进行的操作次数。
• 接下来的 $k$ 行中，每行包含两个整数 $t_{j}$ 和 $i_{j}$，其中 $t_{j} = 1$ 表示操作是删除行，$t_{j} = 2$ 表示操作是删除列。$i_{j}$ 表示在初始编号中进行操作的行或列的编号。

3 3
1 2 3
2 3 1
3 1 2
8

YES
2
1 3
2 3

在第一个样例中，初始表格如下：

$$\begin{array}{|l|l|l|} \hline 1 & 2 & 3 \\ \hline 2 & 3 & 1 \\ \hline 3 & 1 & 2 \\ \hline \end{array} $$

删除第三行和第三列后，得到和为 $8$ 的表格：

$$\begin{array}{|l|l|l|} \hline 1 & 2 & 3 \\ \hline 2 & 3 & 1 \\ \hline 3 & 1 & 2 \\ \hline \end{array} \rightarrow \begin{array}{|l|l|l|} \hline 1 & 2 & 3 \\ \hline 2 & 3 & 1 \\ \hline \end{array} \rightarrow \begin{array}{|l|l|} \hline 1 & 2 \\ \hline 2 & 3 \\ \hline \end{array} $$

2 3
2 2 2
2 2 2
5

NO

在第二个样例中，无法通过允许的操作得到和为 $5$ 的表格。

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

YES
3
1 4
1 5
2 1

在第三个样例中，初始表格如下：

$$\begin{array}{|l|l|l|l|l|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline 5 & 5 & 3 & 2 & 4 \\ \hline 1 & 2 & 4 & 5 & 2 \\ \hline \end{array} $$

删除最后两行和第一列后，得到和为 $34$ 的表格：

$$\begin{array}{|l|l|l|l|l|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline 5 & 5 & 3 & 2 & 4 \\ \hline 1 & 2 & 4 & 5 & 2 \\ \hline \end{array} \rightarrow \begin{array}{|l|l|l|l|l|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline 5 & 5 & 3 & 2 & 4 \\ \hline \end{array} \rightarrow \begin{array}{|l|l|l|l|l|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline \end{array} \rightarrow \begin{array}{|l|l|l|l|} \hline 2 & 1 & 4 & 5 \\ \hline 5 & 4 & 1 & 2 \\ \hline 2 & 4 & 3 & 1 \\ \hline \end{array} $$

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制	子任务依赖
$1$	$17$	$h = 1$
$2$	$6$	每行的数字和不超过该行的编号
$3$	$10$	$h \leq 3$	$1$
$4$	$13$	$h, w \leq 10$
$5$	$13$	$h, w \leq 12$	$4$
$6$	$12$	$a_{i, j} \leq 6$
$7$	$29$	无附加限制	$1\sim 6$