问题描述

Takahashi是一位种植卷心菜的农民，他种了$N$个品牌的卷心菜，分别称为Brand $1$到Brand $N$。他有$A_i$颗Brand $i$的卷心菜$(1 \leq i \leq N)$。这里要注意：所有的卷心菜都是可区分的。

他有$M$个客户，分别称为Company $1$到Company $M$。Company $j$ $(1 \leq j \leq M)$ 订购了$B_j$颗卷心菜。

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

• 如果$c_{i, j} = 1$，表示Brand $i$的卷心菜可以发货给Company $j$；
• 如果$c_{i, j} = 0$，表示Brand $i$的卷心菜无法发货给Company $j$。

如果Takahashi成功决定发往哪个公司的卷心菜，以至于每个公司$j$ $(1 \leq j \leq M)$至少收到$B_j$颗卷心菜，那么他将被称为Cabbage Master。

Snuke决定选择吃掉零颗或多颗卷心菜，以便无论Takahashi把卷心菜发往何处，他都无法获得Cabbage Master的称号。因为他不太喜欢卷心菜，所以他会选择吃掉最少数量的卷心菜，以达到他的目标。

输出Snuke将吃掉的卷心菜数量，并且Snuke选择吃掉卷心菜的方式有多少种（对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}$ $c_{2, 1}$ $c_{2, 2}$ $\ldots$ $c_{2, M}$ $\vdots$ $c_{N, 1}$ $c_{N, 2}$ $\ldots$ $c_{N, M}$

输出格式

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

$X$ $Y$

示例输入1

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

示例输出1

2 6

Snuke将吃掉两颗卷心菜，以阻止Takahashi成为Cabbage Master。有六种方式可以选择要吃掉的卷心菜，如下所示，其中$(i, j)$表示Brand $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)$

示例输入2

1 1
3
4
1

示例输出2

0 1

即使Snuke不吃任何卷心菜，Takahashi也可能无法成为Cabbage Master。然后，Snuke将不吃任何卷心菜，他可以选择其方式只有一种：什么都不吃。

示例输入3

1 3
100
30 30 30
1 1 1

示例输出3

11 892328666

对于Snuke选择要吃掉的卷心菜的方式的数量，一定要对$998244353$取模。