102157: [AtCoder]ABC215 H - Cabbage Master

Problem Statement

Takahashi, a cabbage farmer, has grown $N$ brands of cabbages, called Brand $1$ through Brand $N$. He has $A_i$ heads of cabbage of Brand $i$ $(1 \leq i \leq N)$. Here, all heads of cabbages are distinguishable.
He has $M$ clients called Company $1$ through Company $M$. Company $j$ $(1 \leq j \leq M)$ has ordered $B_j$ heads of cabbages.
Different companies accept different brands of cabbages. For each pair $i, j$ $(1 \leq i \leq N, 1 \leq j \leq M)$,

• if $c_{i, j} = 1$, cabbage of Brand $i$ can be shipped to Company $j$;
• if $c_{i, j} = 0$, cabbage of Brand $i$ cannot be shipped to Company $j$.

Takahashi will be called a Cabbage Master if he succeeds in deciding where to ship the heads of cabbages so that $B_j$ or more heads of cabbages will be shipped to every company $j$ $(1 \leq j \leq M)$.

Snuke has decided to choose and eat zero or more heads of cabbages so that Takahashi cannot get the title of Cabbage Master, regardless of where to ship his cabbages. He does not like cabbage very much, so he will choose to eat the minimum number of heads of cabbages needed to achieve his objective.

Print the number of heads of cabbages Snuke will eat, and the number of ways, modulo $998244353$, for Snuke to choose heads of cabbages to eat. Two ways to choose heads of cabbages are considered different when there is a head of cabbage that is eaten in one way but not in the other. Here, remember that any two heads of cabbages are distinguishable even if they are of the same brand.

Constraints

• $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 \lbrace 0, 1 \rbrace$
• For every $1 \leq j \leq M$, there exists $1 \leq i \leq N$ such that $c_{i, j} = 1$.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$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}$

Output

Print $X$, the number of heads of cabbages Snuke will eat, and $Y$, the number of ways for Snuke to choose heads of cabbages to eat, modulo $998244353$, in this order, with a space in between.

$X$ $Y$

Sample Input 1

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

Sample Output 1

2 6

Snuke will eat two heads of cabbages to prevent Takahashi from becoming a Cabbage Master. There are six such ways to choose heads of cabbages to eat, as shown below, where $(i, j)$ denotes the $j$-th head of cabbage of Brand $i$.

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

Sample Input 2

1 1
3
4
1

Sample Output 2

0 1

It is possible that Takahashi is unable to become a Cabbage Master even if Snuke eats no cabbage. Then, Snuke will eat zero heads of cabbages, and there is just one way for him to choose heads of cabbages to eat: do not eat anything.

Sample Input 3

1 3
100
30 30 30
1 1 1

Sample Output 3

11 892328666

For the number of ways for Snuke to choose heads of cabbages to eat, be sure to print it modulo $998244353$.

问题描述

菜农高桥种植了$N$种卷心菜，分别称为品牌$1$到品牌$N$。他有$A_i$个品牌$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$个或更多的卷心菜头，那么他将被称为卷心菜大师。

森克决定选择并吃掉零个或多个卷心菜头，以便无论将卷心菜头运送到哪里，高桥都不能获得卷心菜大师的称号。他不太喜欢卷心菜，所以他将选择吃掉实现目标所需的最小数量的卷心菜头。

打印森克将吃的卷心菜头的数量，以及森克选择吃掉的卷心菜头的方式的数量，模$998244353$。当有一种卷心菜头在一种选择中被吃掉，但在另一种选择中没有被吃掉时，两种选择卷心菜头的方式被认为是不同的。在这里，请记住，即使是同一品牌的卷心菜头，也是可区分的。

约束条件

• $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 \lbrace 0, 1 \rbrace$
• 对于每一个$1 \leq j \leq M$，都存在$1 \leq i \leq N$，使得$c_{i, j} = 1$。
• 输入中的所有值都是整数。

输入

输入将从标准输入中以以下格式给出：

$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}$