卷心菜大师

题目描述

高桥君是一位卷心菜农，培育了 $N$ 个品牌的卷心菜，称为品牌 $1$ 到品牌 $N$。他有 $A_i$ 颗品牌 $i$ 的卷心菜 $(1 \le i \le N)$。这里，所有卷心菜都是可区分的。

他有 $M$ 个客户，称为公司 $1$ 到公司 $M$。公司 $j$ $(1 \le j \le M)$ 订购了 $B_j$ 颗卷心菜。

不同公司接受不同品牌的卷心菜。对每一对 $i, j$ $(1 \le i \le N, 1 \le j \le M)$：

• 如果 $c_{i, j} = 1$，品牌 $i$ 的卷心菜可以运往公司 $j$；
• 如果 $c_{i, j} = 0$，品牌 $i$ 的卷心菜不能运往公司 $j$。

如果高桥君能决定卷心菜的运送方式，使得每家公司的发货量都达到 $B_j$ 颗或以上，那么他就会被称作卷心菜大师。

Snuke 决定吃掉 0 颗或多颗卷心菜，使得无论高桥君如何运送卷心菜，他都无法获得卷心菜大师的称号。Snuke 不太喜欢卷心菜，所以他会选择吃下达成目标所需的最少颗数。

输出 Snuke 吃掉的卷心菜颗数，以及 Snuke 选择吃掉哪些卷心菜的方式数对 $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}$

输出格式

按顺序输出 Snuke 吃掉的卷心菜颗数 $X$ 和选择方式数 $Y$（对 $998244353$ 取模），中间用空格隔开。

$X$ $Y$

样例

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

2 6

Snuke 将吃掉两颗卷心菜，使高桥君无法成为卷心菜大师。吃掉卷心菜的选择方式共有 6 种，如下所示，其中 $(i, j)$ 表示品牌 $i$ 的第 $j$ 颗卷心菜。

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

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

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

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

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

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

1 1
3
4
1

0 1

即使 Snuke 不吃任何卷心菜，高桥君也可能无法成为卷心菜大师。 此时 Snuke 吃掉 0 颗卷心菜，而选择吃掉哪些卷心菜的方式只有 1 种：什么都不吃。

1 3
100
30 30 30
1 1 1

11 892328666

对于 Snuke 选择吃掉哪些卷心菜的方式数，注意要对 $998244353$ 取模。

数据范围

• $1 \le N \le 20$
• $1 \le M \le 10^4$
• $1 \le A_i \le 10^5$
• $1 \le B_j \le 10^5$
• $c_{i, j} \in \lbrace 0, 1 \rbrace$
• 对每个 $1 \le j \le M$，存在满足 $c_{i, j} = 1$ 的 $1 \le i \le N$。
• 输入中的所有值均为整数。