题目描述

キャベツ農家の高橋君は、品種 $1$ から品種 $N$ までの $N$ 種類のキャベツを育てました。高橋君は品種 $i$ $(1\ \leq\ i\ \leq\ N)$ のキャベツを $A_i$ 個持っています。ここで、 すべてのキャベツは区別できます。
キャベツの卸先として会社 $1$ から会社 $M$ までの $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$ で割ったあまりの $2$ つを出力してください。
ただし、 キャベツの選び方が異なるとは、一方の選び方で食べられたがもう一方の選び方で食べられていないようなキャベツが存在することをいいます。ここで、異なる $2$ つのキャベツは 品種が同じでも区別される ことに注意してください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

题目大意

有 $n$ 种颜色的，第 $i$ 种有 $a_i$ 个，任意两球互不相同。还有 $m$ 个盒子，每个盒子可以被放入某些颜色的小球，且第 $i$ 个盒子要求放入总数不少于 $b_i$。你要拿走尽量少的球，使得要求无法被满足，并求出此时拿球方案数模 $998244353$ 的值。

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

2 6

1 1
3
4
1

0 1

1 3
100
30 30 30
1 1 1

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\ \lbrace\ 0,\ 1\ \rbrace$
• 任意の $1\ \leq\ j\ \leq\ M$ に対して、ある $1\ \leq\ i\ \leq\ N$ が存在して $c_{i,\ j}\ =\ 1$ が成り立つ
• 入力はすべて整数

Sample Explanation 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)$

Sample Explanation 2

すぬけ君がキャベツを $1$ 個も食べなくても、高橋君がキャベツ名人になることができない場合もあります。 このとき、すぬけ君が食べるキャベツの個数は $0$ 個であり、すぬけ君が食べるキャベツの組み合わせとして考えられるのは、「どのキャベツも食べない」という $1$ 通りのみです。

Sample Explanation 3

すぬけ君が食べるキャベツの選び方が何通りあるかについては、 $998244353$ で割ったあまりを出力することに注意してください。