你需要击败 $n$ 个敌人。每个敌人 $i$ 拥有 $a_i$ 点生命值和 $b_i$ 点护甲值。你可以使用攻击来击败敌人。对于每一次攻击，你可以选择对所有敌人造成 $x$ 点伤害，其中 $1 \le x \le k$。造成 $x$ 点伤害的每次攻击花费为 $c_x$。你可以进行任意次数的攻击。

当敌人受到伤害时，伤害首先由其护甲吸收。当护甲被摧毁后，任何剩余的伤害不会作用于生命值。形式化地，当敌人 $i$ 受到 $y$ 点伤害时，会发生以下情况：

• 如果 $b_i > 0$，$b_i$ 减少 $y$。
• 否则，$a_i$ 减少 $y$。
• 如果任何时刻 $a_i \le 0$，则认为敌人 $i$ 被击败。

你的任务是确定击败所有敌人所需的最小总花费，以及达到此最小花费的不同攻击策略（攻击组合）的数量，结果对 $998\,244\,353$ 取模。

策略是一个整数数组 $x_1, x_2, \dots, x_m$ ($1 \le x_i \le k$)，表示每次攻击造成的伤害。当且仅当数组 $x$ 不同时，两种策略被视为不同。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 1000$)，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n, m$ ($1 \le n \le 5 \cdot 10^5, 1 \le m \le 10^4$)，分别表示敌人的数量，以及生命值和护甲值的最大值。

接下来的两行包含两个整数数组 $a$ 和 $b$ ($1 \le a_i, b_i \le m$)，每个数组长度为 $n$，分别表示敌人的生命值和护甲值。

接下来一行包含一个整数 $k$ ($1 \le k \le 100$)，表示单次攻击可能造成的最大伤害。

随后是一个长度为 $k$ 的整数数组 $c$ ($1 \le c_i \le 10^9$)，其中第 $i$ 个整数 $c_i$ 表示对所有敌人造成 $i$ 点伤害的花费。

保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$，$m$ 的总和不超过 $10^4$。

输出格式

对于每个测试用例，输出一行，包含两个整数：击败所有敌人所需的最小总花费，以及达到此花费的不同策略数量，对 $998\,244\,353$ 取模。

样例

输入 1

4
5 5
3 5 2 1 2
3 1 3 2 3
3
2 3 4
3 2
2 2 2
2 2 2
3
2 3 3
7 6
5 3 4 6 6 3 4
4 6 4 2 3 5 5
4
2 4 6 7
10 100
38 49 79 66 49 89 21 55 13 23
67 56 26 39 56 16 84 50 92 82
11
6 6 7 8 9 9 9 9 9 9 9

输出 1

9 1
6 4
18 18
99 44387