C

题目描述

教室里的一些同学正在进行“撕纸”比赛，小 C 在一旁围观。

纸的微观结构可以视为一个方形网格。对于相邻点之间的有向边 $(u,v)$，给定一个参数 $f(u,v)$。注意，$f(u,v)$ 可能不等于 $f(v,u)$。

当纸裂开时，设左侧纸片上的点集为 $L$，右侧纸片上的点集为 $R$。所有从左侧纸片指向右侧纸片的有向边都将被拉断，需要耗费的拉力为

$$\sum_{\substack{u\in L,\ v\in R\\(u,v)\in E}} f(u,v).$$

纸总会按照所需拉力最小的方式裂开。

你需要求出最小拉力，以及能够达到最小拉力的裂口方案数。

形式化定义

有一张包含

$$n\times(m+2)$$

个点的有向图。每个点用二元组 $(i,j)$ 表示，其中

$$1\le i\le n,\qquad 0\le j\le m+1.$$

用 $(u,v,w)$ 表示一条从点 $u$ 指向点 $v$、权值为 $w$ 的有向边。图中包含以下四类边。

1. 对于所有满足 $1\le i\le n$、$1\le j\le m$ 的整数 $i,j$，存在有向边

   $$(i,j)\longrightarrow\bigl((i\bmod n)+1,j\bigr),$$

   其权值为 $a_{i,j}$。

2. 对于所有满足 $1\le i\le n$、$0\le j\le m$ 的整数 $i,j$，存在有向边

   $$(i,j)\longrightarrow(i,j+1),$$

   其权值为 $b_{i,j}$。

3. 对于所有满足 $1\le i\le n$、$1\le j\le m$ 的整数 $i,j$，存在有向边

   $$\bigl((i\bmod n)+1,j\bigr)\longrightarrow(i,j),$$

   其权值为 $c_{i,j}$。

4. 对于所有满足 $1\le i\le n$、$0\le j\le m$ 的整数 $i,j$，存在有向边

   $$(i,j+1)\longrightarrow(i,j),$$

   其权值为 $d_{i,j}$。

将点集

$$S=\{(i,0)\mid 1\le i\le n\}$$

中的所有点视为源点，将点集

$$T=\{(i,m+1)\mid 1\le i\le n\}$$

中的所有点视为汇点。

你需要求源点集合 $S$ 与汇点集合 $T$ 之间的最小割代价，以及达到最小割代价的不同割方案数。

方案数对

$$998244353$$

取模。

输入格式

第一行输入一个整数 $\mathrm{id}$，表示测试点编号。

接下来包含若干组测试数据。对于每组测试数据：

• 第一行输入两个正整数 $n,m$；

• 接下来 $n$ 行，每行输入 $m$ 个整数，第 $i$ 行依次为

  $$a_{i,1},a_{i,2},\ldots,a_{i,m};$$

• 接下来 $n$ 行，每行输入 $m+1$ 个整数，第 $i$ 行依次为

  $$b_{i,0},b_{i,1},\ldots,b_{i,m};$$

• 接下来 $n$ 行，每行输入 $m$ 个整数，第 $i$ 行依次为

  $$c_{i,1},c_{i,2},\ldots,c_{i,m};$$

• 接下来 $n$ 行，每行输入 $m+1$ 个整数，第 $i$ 行依次为

  $$d_{i,0},d_{i,1},\ldots,d_{i,m}.$$

最后一行输入：

0 0

表示输入结束。

不同测试数据之间可能存在空行，读取时将其视为普通空白字符即可。

输出格式

对于每组测试数据，输出一行两个整数：

• 第一个整数表示最小割代价；
• 第二个整数表示最小割方案数对 $998244353$ 取模后的结果。

数据范围与约定

每个测试点有一个对应参数 $N$。

对于所有测试数据：

$$n,m\le N,\qquad T\le 5.$$

所有边权均满足

$$1\le a_{i,j},b_{i,j},c_{i,j},d_{i,j}\le 2\times 10^9.$$

对于每个测试点，除第一组测试数据外，其余各组测试数据均满足

$$n,m\le \frac{N}{2}.$$

特殊性质如下：

• 性质 A：在所有最小割方案中，第一行恰好只有边 $(1,0)\to(1,1)$ 被割掉；

• 性质 B：对于所有合法的 $i,j$，均有

  $$a_{i,j}=c_{i,j},\qquad b_{i,j}=d_{i,j};$$

• 性质 C：所有边权均在区间 $[1,10^9]$ 内随机生成。

测试点编号 $\mathrm{id}$	$N$	特殊性质
$1$	$2$	无
$2$	$4$
$3\sim4$	$16$
$5$	$130$	C
$6$		A、B
$7\sim9$		A
$10\sim17$	$32+14(\mathrm{id}-10)$	B
$18\sim25$	$32+14(\mathrm{id}-18)$	无