Maximize Total Value

You are given n types of items. For each item of type \( i \), its value is \( v_i \) and its count is \( c_i \). You are also given an exchange cost \( x_i \) for every type \( i \) (with \( 1 \le i \le n-1 \)).

The total value is defined as \( \sum_{i=1}^n c_i \cdot v_i \). You can perform some operations (possibly zero) to maximize the total value. An operation is defined as follows:

Choose an index \( i \) (with \( 1 \le i \le n-1 \)) such that \( c_i \ge x_i \). Then update: \[ \begin{aligned} c_i &\gets c_i - x_i, \\ c_{i+1} &\gets c_{i+1} + 1. \end{aligned} \]

Note: You need to maximize the total value first, and then output the answer modulo \( 998\,244\,353 \). That is, compute \( (\text{maximum total value}) \bmod 998\,244\,353 \).

Hint: An operation is beneficial only if it increases the total value, i.e. when \( v_{i+1} - x_i \cdot v_i > 0 \). Use this observation to greedily perform as many beneficial operations as possible from type 1 to type \( n-1 \).

inputFormat

The first line contains a single integer \( n \) --- the number of item types.

The second line contains \( n \) space-separated integers \( v_1, v_2, \ldots, v_n \) --- the values of the items.

The third line contains \( n \) space-separated integers \( c_1, c_2, \ldots, c_n \) --- the counts of the items.

The fourth line contains \( n-1 \) space-separated integers \( x_1, x_2, \ldots, x_{n-1} \) where \( x_i \) denotes the number of items of type \( i \) required to perform an operation to convert them into one item of type \( i+1 \).

outputFormat

Output a single integer --- the maximum total value obtainable after performing operations optimally, taken modulo \( 998\,244\,353 \).

sample

3
1 3 10
3 0 0
2 2

4