Problem Description

To commemorate the discontinued Code Jam, Little $\beth$ is preparing a “Code Blockage Memorial Contest”. Little $\beth$'s friend Little $\mho$ also comes to watch, so Little $\beth$ wants to predict Little $\mho$'s result.

The contest lasts $T$ seconds and has $n$ problems. The score of problem $i(1 \le i \le n)$ is $a_i$, and Little $\beth$ predicts that Little $\mho$ needs $t_i$ seconds to finish it.

There are two types of problems: visible-result and invisible-result. For an invisible-result problem, you can only know the judging result after the contest ends, while for a visible-result problem, you get the judging result immediately after submission. Little $\beth$ has not yet decided the type of each problem.

Since Little $\mho$ never writes a checker for stress testing, they will first finish all visible-result problems in increasing order of index, and then finish all invisible-result problems in increasing order of index. Little $\mho$ will spend $t_i$ seconds to finish problem $i$. If the total time spent on problem $i$ and all problems finished before it is not greater than $T$, then Little $\mho$ will make a submission on problem $i$.

Since every submission by Little $\mho$ is accepted (AC), Little $\beth$ wants to know, over all $2^n$ ways to determine the types of the $n$ problems, the sum of the total scores that Little $\mho$ can get. Since the answer can be very large, output it modulo $998244353$.

Input Format

The first line contains three integers $c, n, T$, representing the test point index, the number of problems, and the contest duration. In the sample, $c$ indicates that it satisfies the same constraints as test point $c$.

The second line contains $n$ integers $a_1, a_2, \cdots , a_n$, representing the score of each problem.

The third line contains $n$ integers $t_1, t_2, \cdots , t_n$, representing the time Little $\mho$ needs for each problem.

Output Format

Output one integer, representing, over all ways to determine the problem types, the sum of the total scores Little $\mho$ can obtain, modulo $998244353$.

1 3 3
2 3 4
1 2 2

40

Hint

Sample 1 Explanation

We use a $01$ sequence of length $3$ to represent the problem types, where $1$ means visible-result and $0$ means invisible-result.

• $(0, 0, 0)(1, 0, 0)(1, 1, 0)(1, 1, 1)$: in these four cases, Little $\mho$ solves problems in increasing order of index, submissions are made on the first two problems, and the score sum is $5$.
• $(0, 1, 0)$: Little $\mho$ solves in the order $213$, submissions are made on the first two solved problems, and the score sum is $5$.
• $(0, 0, 1)$: Little $\mho$ solves in the order $312$, submissions are made on the first and third problems, and the score sum is $6$.
• $(1, 0, 1)$: Little $\mho$ solves in the order $132$, submissions are made on the first and third problems, and the score sum is $6$.
• $(0, 1, 1)$: Little $\mho$ solves in the order $231$, only the second problem has a submission, and the score sum is $3$.

Therefore, the answer is $(5 \times 4 + 5 + 6 + 6 + 3) \bmod 998244353 = 40$.

Constraints

For all testdata:

• $1\le n\le 200$.
• $1\le T\le 3\times 10^5$.
• $\forall 1\le i\le n , 1\le a_i\le 3\times 10^5$.
• $\forall 1\le i\le n, 1\le t_i\le T$.

• Special Property A: $\forall 1 \le i \le n, a_i = 1$.
• Special Property B: $\forall 1 \le i \le n, t_i = 1$.

Afterword

“Why are all problems in your contest invisible-result?”

Translated by ChatGPT 5