AT_abc215_h [ABC215H] Cabbage Master

题目描述

卷心菜农户高桥君种植了 $N$ 个品种（从 $1$ 到 $N$）的卷心菜。高桥君拥有品种 $i$ 的卷心菜 $A_i$ 个（$1 \leq i \leq N$）。这里，所有的卷心菜都是可以区分的。

作为卷心菜的批发对象，有 $M$ 个公司（从 $1$ 到 $M$），公司 $j$（$1 \leq j \leq M$）下单了 $B_j$ 个卷心菜。

每个公司可以收购的卷心菜品种各不相同。对于所有的 $i, j$ 组合（$1 \leq i \leq N, 1 \leq j \leq M$）：

• 当 $c_{i, j} = 1$ 时，品种 $i$ 的卷心菜可以出货给公司 $j$。
• 当 $c_{i, j} = 0$ 时，品种 $i$ 的卷心菜不能出货给公司 $j$。

如果高桥君能够合理分配所有卷心菜的出货对象，使得对每个公司 $j$（$1 \leq j \leq M$）都能出货不少于 $B_j$ 个卷心菜，则他可以获得“卷心菜大师”的称号。

すぬけ君为了让高桥君无论如何都无法获得“卷心菜大师”的称号，可以选择吃掉 $0$ 个或更多的卷心菜。すぬけ君不喜欢卷心菜，他会选择吃掉的卷心菜数量最少的方案。

请输出すぬけ君需要吃掉的卷心菜的最少数量，以及吃掉卷心菜的方案数对 $998244353$ 取模的结果。

注意，吃掉卷心菜的方案不同，指的是存在某个卷心菜在一种方案中被吃掉，而在另一种方案中没有被吃掉。这里要注意，即使是同一品种的不同卷心菜也是可以区分的。

输入格式

输入通过标准输入给出，格式如下：

$N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_M$ $c_{1, 1}$ $c_{1, 2}$ $\ldots$ $c_{1, M}$ $c_{2, 1}$ $c_{2, 2}$ $\ldots$ $c_{2, M}$ $\vdots$ $c_{N, 1}$ $c_{N, 2}$ $\ldots$ $c_{N, M}$

输出格式

请输出すぬけ君需要吃掉的卷心菜的最少数量 $X$，以及吃掉卷心菜的方案数对 $998244353$ 取模的结果 $Y$，用空格隔开。

$X$ $Y$

输入输出样例 #1

输入 #1

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

输出 #1

2 6

输入输出样例 #2

输入 #2

1 1
3
4
1

输出 #2

0 1

输入输出样例 #3

输入 #3

1 3
100
30 30 30
1 1 1

输出 #3

11 892328666

说明/提示

限制条件

• $1 \leq N \leq 20$
• $1 \leq M \leq 10^4$
• $1 \leq A_i \leq 10^5$
• $1 \leq B_j \leq 10^5$
• $c_{i, j} \in \{0, 1\}$
• 对于任意 $1 \leq j \leq M$，存在某个 $1 \leq i \leq N$ 使得 $c_{i, j} = 1$
• 输入均为整数

样例解释 1

为了让高桥君无法成为卷心菜大师，すぬけ君需要吃掉 $2$ 个卷心菜。以“品种 $i$ 的第 $j$ 个卷心菜”记作 $(i, j)$，すぬけ君可以吃掉的卷心菜组合有如下 $6$ 种：

• $(1, 1), (1, 2)$
• $(1, 1), (2, 1)$
• $(1, 1), (2, 2)$
• $(1, 2), (2, 1)$
• $(1, 2), (2, 2)$
• $(2, 1), (2, 2)$

样例解释 2

有时，即使すぬけ君一颗卷心菜都不吃，高桥君也无法成为卷心菜大师。这时，すぬけ君需要吃掉的卷心菜数量为 $0$，吃掉卷心菜的方案数为 $1$（即什么都不吃）。

样例解释 3

请注意，吃掉卷心菜的方案数需要对 $998244353$ 取模后输出。

由 ChatGPT 4.1 翻译