410703: GYM104081 D Devil May Cry

​在 YahAHa 很喜欢的游戏《Devil May Cry》系列中，有一个角色 Dante ，拥有非常多的武器和招式。举例来说，在《Devil May Cry 5》中，Dante 有六把近战武器，六把远程武器，四种战斗风格，三种战斗形态。

每种武器，风格和战斗形态，都将赋予 Dante 不同的技能，因此，Dante拥有极为丰富的技能（超过200！），利用这些丰富的技能，你可以打出各种各样的花式连招。

现在，YahAHa 想要设计一些Dante的连招，连招由若干个依次释放的技能组成，假如在某个连招中一共释放了 $$$n$$$ 个技能，则这个连招可以描述成一个下标从 $$$1$$$ 开始的长度为 $$$n$$$ 的数列 $$$a$$$ ，数列中的每个项都是一个正整数，代表一个技能。

一个合法的连招要满足如下条件：

- YahAHa 只想用 $$$m$$$ 个技能组成连招，因此对于任意的 $$$1\leq i\leq n$$$ 要满足 $$$1\leq a_i\leq m$$$ （不必每个技能都用上）, $$$m$$$ 由输入给出。

- 同一个技能不能释放太多次，因为那样会导致评分降低，若用 $$$cnt_i$$$ 表示连招中技能 $$$i$$$ 出现的次数，则对于任意的 $$$1\leq i\leq m$$$ ，要满足 $$$cnt_i\leq lim_i$$$ ，其中 $$$lim_i$$$ 由输入给出。

- 有些技能有释放限制，例如：只能在空中释放，因此在连招的某些特定位置不能释放某个技能，具体而言，有若干形如 $$$ a_{p_i}\neq s_i $$$ 的限制，$$$p_i$$$ 和 $$$s_i$$$ 由输入给出。

现在 YahAHa 想知道，有多少长度为 $$$n$$$ 的合法连招？由于他还想去打游戏，所以他让你帮他解决这个问题。由于答案可能会很大，YahAHa 只想知道答案对 $$$998244353$$$ 取模的结果。

​第一行包括两个整数 $$$n,m$$$（ $$$1\leq n\leq 20,1\leq m\leq 100$$$ )

​接下来一行，包括 $$$m$$$ 个整数，其中第 $$$i$$$ 个数表示 $$$lim_i$$$ ，表示第二条限制 ( $$$0\leq lim_i\leq n$$$ )。

​接下来一行包括一个整数 $$$r$$$ ( $$$0\leq r\leq 1000$$$ ）

​接下来 $$$r$$$ 行，每行两个正整数 $$$p_i,s_i$$$ ，表示第三条限制，$$$1\leq p_i\leq n，1\leq s_i\leq m$$$ 。

​仅一个整数，表示答案对 $$$998244353$$$ 取模的值

1 1
1
0

1

2 3
2 2 1
2
2 1
2 2

2

3 4
1 3 2 2
3
3 3
3 4
1 1

21