题目描述

给定 $n$ 种物品，每种物品 $i$ 价值为 $v_i$，个数为 $c_i$。

定义总价值为 $\sum\limits_{i=1}^nc_iv_i$，你可以进行一些（可能为 $0$）次操作来最大化总价值。

一次操作为：选定一个 $i$ 满足 $c_i \geq x_i$，让 $c_i\gets c_i - x_i$，$c_{i+1}\gets c_{i+1}+ 1$。

输出最大的总价值对 $998,\!244,\!353$ 取模。

注意，你需要最大化总价值，再对 $998,\!244,\!353$ 取模，而不是最大化「总价值对 $998,\!244,\!353$ 取模的值」。

输入格式

本题有多组数据。

第一行一个正整数 $\text{sid}$，表示该测试数据所属子任务编号。

第二行一个正整数 $t$，表示数据组数。对于每组数据：

• 输入共四行。
• 第一行，一个正整数 $n$，表示钱的种数。
• 第二行，$n$ 个非负整数分别表示 $v_1, v_2 \dots v_n$。
• 第三行，$n$ 个非负整数分别表示 $c_1, c_2 \dots c_n$。
• 第四行，$n - 1$ 个正整数分别表示 $x_1, x_2 \dots x_{n - 1}$。

输出格式

输出 $t$ 行，每行一个整数，表示物品总价值的最大值。所有答案对 $998244353$ 取模。

输入输出样例 #1

输入 #1

0
2
2
1 5
5 1
4
10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

输出 #1

11
172998509

说明/提示

样例解释

对于样例的第一组数据，$v=[1,5]$，$c=[5,1]$，$x=[4]$。可以选定 $i=1$ 进行一次操作，此时 $c=[1,2]$，总价值为 $1\cdot 1+5\cdot 2=11$，可以证明它是最大的。

数据规模与约定

本题采用捆绑测试。

下面是各 Subtask 的特殊性质，斜杠表示该栏无特殊限制。

• 特殊性质 A：$x_i = 10^9$。
• 特殊性质 B：$x_i = 1$。
• 特殊性质 C：所有 $c_i, v_i$ 均在 $[0, 10^5]$ 间均匀随机生成；所有 $x_i$ 均在 $[1, 10^5]$ 间均匀随机生成。

对于所有数据，$1\le t \le 10^5$，$2\le n$，$\sum n\le 2\times 10^5$，$1\le x_i\le 10^9$，$0\le c_i,v_i\le 10^9$。