Background

Little E finally got back her New Year’s money that her mom had been keeping for her today.

As a far-sighted collector, Little E knows that if she starts collecting things from now on, they will become valuable in the future.

In Little E’s world, there are some banknotes. She knows their future value, but unfortunately, these banknotes can only be exchanged from smaller to larger. What should she do?

Problem Description

You are given $n$ types of items. For each item $i$, its value is $v_i$ and its quantity is $c_i$.

Define the total value as $\sum\limits_{i=1}^n c_i v_i$. You may perform some (possibly $0$) operations to maximize the total value.

One operation is: choose an $i$ such that $c_i \geq x_i$, set $c_i \gets c_i - x_i$, and $c_{i+1} \gets c_{i+1} + 1$.

Output the maximum total value modulo $998,\!244,\!353$.

Note: You need to maximize the total value first, and then take modulo $998,\!244,\!353$, rather than maximizing “(total value modulo $998,\!244,\!353$)”.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $\text{sid}$, indicating the subtask ID of this testdata.

The second line contains a positive integer $t$, indicating the number of test cases. For each test case:

• The input consists of four lines.
• The first line contains a positive integer $n$, the number of types of money.
• The second line contains $n$ non-negative integers: $v_1, v_2 \dots v_n$.
• The third line contains $n$ non-negative integers: $c_1, c_2 \dots c_n$.
• The fourth line contains $n - 1$ positive integers: $x_1, x_2 \dots x_{n - 1}$.

Output Format

Output $t$ lines. Each line contains one integer, the maximum total value of the items. All answers are taken modulo $998244353$.

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

11
172998509

Hint

Sample Explanation

For the first test case of the sample, $v=[1,5]$, $c=[5,1]$, $x=[4]$. You can choose $i=1$ and perform one operation. Then $c=[1,2]$, and the total value is $1\cdot 1+5\cdot 2=11$. It can be proven that this is the maximum.

Constraints and Notes

This problem uses bundled tests.

Below are the special properties of each Subtask. A slash indicates no special restriction in that column.

• Special Property A: $x_i = 10^9$.
• Special Property B: $x_i = 1$.
• Special Property C: all $c_i, v_i$ are generated uniformly at random in $[0, 10^5]$; all $x_i$ are generated uniformly at random in $[1, 10^5]$.

For all testdata, $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$.

upd: One more hack testdata set was added, with $\text{sid}$ equal to $7$.

Translated by ChatGPT 5