Code Block Commemoration Contest Score Prediction

In memory of the canceled CodeJam, little $\beth$ organizes a Code Block Commemoration Contest. There are $n$ problems and the contest lasts for $T$ seconds. The $i$-th problem has a score of $a_i$ and is predicted by $\beth$ to be solved by little $\mho$ in $t_i$ seconds.

The problems have two types: result visible and result invisible. For result invisible problems, the evaluation result is revealed only after the contest ends, whereas for result visible problems the result is known immediately upon submission. Little $\beth$ has not decided the type of each problem yet.

Little $\mho$ will solve all the result visible problems first (in increasing order of their indices) and then solve all the result invisible problems (again in increasing order). He spends exactly $t_i$ seconds on the $i$-th problem. Moreover, if the cumulative time spent on the $i$-th problem and all previously solved problems does not exceed $T$, a submission (which is always accepted) is generated for the $i$-th problem.

For a given type assignment for the $n$ problems (a total of $2^n$ possibilities), let the score be the sum of scores $a_i$ for all problems that were submitted (i.e. solved before or at time $T$). The task is to compute the sum of scores over all $2^n$ possible assignments, modulo $998244353$.

inputFormat

The first line contains two integers $T$ and $n$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, where $a_i$ is the score of the $i$-th problem.

The third line contains $n$ integers $t_1, t_2, \ldots, t_n$, where $t_i$ is the time (in seconds) required to solve the $i$-th problem.

outputFormat

Output one integer: the sum of scores over all $2^n$ type assignments modulo $998244353$.

sample

5 1
10
3

20