题目描述

劳埃德先生为了应对阿尼亚的入学面试，决定带阿尼亚出萌，让她增长见闻，学习上流社会的常识。但是阿尼亚只对出萌感兴趣，她走在路上突然注意到了街边有 $n$ 个小球，每个小球有一个重量 $w_i$，旁边有一个奇怪的球桌，这个球桌分别在四个角落里各有一个洞，有趣的是，其中两个洞是方形的，另外两个洞是圆形的，这四个洞分别属于两位玩家 $A, B$，每个玩家各自拥有一个方洞和一个圆洞，球会从洞中掉进对应玩家的袋子里。

阿尼亚把小球依次放到洞里面去，她发现了一些规律：

• 每位玩家的袋子只能承受一定重量的小球，玩家 $A$ 的袋子只能承受 $P_1$ 重量的小球，玩家 $B$ 的袋子只能承受 $P_2$ 重量的小球。
• 掉进每种形状的洞里的小球也有一定重量的限制，掉入方形洞的小球重量之和不能超过 $Q_1$，掉入圆形洞的小球重量之和不能超过 $Q_2$。
• 小球是有类型之分的，一共有 $d$ 种类型，同一种类型的小球不能同时出现在两个玩家的洞里面。

突然球台中间出现了一个魔法洞，小球也可以掉入魔法洞，但是魔法洞不属于任何一个玩家，魔法洞会对四周的四个洞都会产生影响：

• 放入 $A$ 玩家的和放入魔法洞的小球重量之和不能超过 $R_1$。
• 放入 $B$ 玩家的和放入魔法洞的小球重量之和不能超过 $R_2$。
• 放入方洞的和放入魔法洞的小球重量之和不能超过 $R_3$。
• 放入圆洞的和放入魔法洞的小球重量之和不能超过 $R_4$。

但是魔法洞至多只能放入 $c$ 个小球，如果超过了 $c$ 个小球魔法洞将不受控制！

劳埃德先生看到阿尼亚对这个桌球游戏产生了很浓厚的兴趣，于是想考考阿尼亚：让阿尼亚把所有小球放入洞里，有多少种情况能够使得所有袋子和洞的重量限制、魔法洞的重量限制和类型的限制都能够得到满足？

会读心术的阿尼亚立马明白了父亲的意图，但是阿尼亚只会哇酷哇酷，于是她把这个问题交给了你。

答案对 $998244353$ 取模。

输入格式

第一行两个整数 $n, d$，表示小球的个数和类型数。

第二行 $n$ 个整数 $w_i$，表示小球的重量。

第三行 $n$ 个整数 $b_i$，表示小球的类型，保证 $b_i\in [1, d]$。

第四行 $9$ 个整数 $P_1, P_2, Q_1, Q_2, R_1, R_2, R_3, R_4, c$，含义见上述。

输出格式

对于每组数据输出一行整数，表示合法的方案数。

样例 1

Input

5 3
3 3 3 3 4
1 2 2 2 3
8 11 10 12 22 9 11 22 0

Output

21

样例 2

Input

5 3
3 3 3 3 4
1 2 2 2 3
8 9 10 12 14 12 11 11 1

Output

80

样例 3-7

见下发文件 ex_odekeke3.in/ans，ex_odekeke4.in/ans，ex_odekeke5.in/ans，ex_odekeke6.in/ans，ex_odekeke7.in/ans。

数据范围

设 $m = \max\{P_1, P_2, Q_1, Q_2, R_1, R_2, R_3, R_4\}$。

对于 $100\%$ 的数据，保证 $n\le 1500, m\le 100000, c\in [0, 1], d\le n, w_i\le 100$。

下发文件