A - Use Udon Coupon 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 700 点

問題文

正整数 N, L, R と長さ N の正整数列 A = (A_{1}, A_{2}, \dots, A_{N}), B = (B_{1}, B_{2}, \dots, B_{N}) が与えられます。

空で初期化された数列 Q と、 0 で初期化された変数 C と、 1 で初期化された変数 i を用いて以下の操作を 2N 回行います。

  • 以下の行動 1, 2 のうち、いずれかを選んで行う。
    • 行動 1 : Q の末尾に i を挿入し、C を \max(0, C - A_{i}) に置き換える。その後、i を 1 増やす。この行動は、操作前の i が N 以下のときのみ行える。
    • 行動 2 : Q の先頭の数を x として、C に B_{x} を加算する。その後、Q の先頭の要素を削除する。この行動は、操作前の Q が空でないときのみ行える。

2N 回の操作の方法であって、最終的な C が L 以上 R 以下であるようなものの場合の数を 998244353 で割ったあまりを求めてください。

制約

  • 1\leq N\leq 5000
  • 1\leq L \leq R \leq \sum B
  • 1\leq A_{i}\leq 5000
  • 1\leq B_{i}\leq 5000
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられます。

N L R
A_{1} A_{2} \dots A_{N}
B_{1} B_{2} \dots B_{N}

出力

答えを出力してください。

入力例 1

2 100 1000
2001 167
924 178

出力例 1

1

例えば以下のように 4 回の操作を行うことができます。

  • 行動 1 をする。Q = (1), C = 0, i = 2 と変化する。
  • 行動 2 をする。Q = (), C = 924, i = 2 と変化する。
  • 行動 1 をする。Q = (2), C = 757, i = 3 と変化する。
  • 行動 2 をする。Q = (), C = 935, i = 3 と変化する。

上記のように操作すると、最終的な C が 100 以上 1000 以下になります。そのような操作方法はこれしかないので、1 を出力します。

入力例 2

3 10 10
1 6 7
9 2 4

出力例 2

0

入力例 3

15 167 924
122 122 111 85 97 108 115 82 84 82 105 103 113 102 135
116 122 110 106 71 85 70 94 86 110 73 97 101 86 73

出力例 3

9576277

Score : 700 points

Problem Statement

You are given positive integers N, L, R and length-N positive integer sequences A = (A_{1}, A_{2}, \dots, A_{N}), B = (B_{1}, B_{2}, \dots, B_{N}).

Using a sequence Q initialized as empty, a variable C initialized to 0, and a variable i initialized to 1, perform the following operation 2N times.

  • Choose one of the following actions 1, 2 and perform it.
    • Action 1 : Insert i at the end of Q, replace C with \max(0, C - A_{i}). Then, increase i by 1. This action can only be performed when i before the operation is at most N.
    • Action 2 : Let x be the first number in Q, and add B_{x} to C. Then, remove the first element of Q. This action can only be performed when Q before the operation is not empty.

Find the number, modulo 998244353, of ways to perform 2N operations such that the final value of C is between L and R, inclusive.

Constraints

  • 1\leq N\leq 5000
  • 1\leq L \leq R \leq \sum B
  • 1\leq A_{i}\leq 5000
  • 1\leq B_{i}\leq 5000
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N L R
A_{1} A_{2} \dots A_{N}
B_{1} B_{2} \dots B_{N}

Output

Output the answer.

Sample Input 1

2 100 1000
2001 167
924 178

Sample Output 1

1

For example, you can perform four operations as follows.

  • Perform action 1. Then, Q = (1), C = 0, i = 2.
  • Perform action 2. Then, Q = (), C = 924, i = 2.
  • Perform action 1. Then, Q = (2), C = 757, i = 3.
  • Perform action 2. Then, Q = (), C = 935, i = 3.

Performing operations as above makes the final value of C between 100 and 1000 (inclusive). This is the only such way to perform operations, so output 1.

Sample Input 2

3 10 10
1 6 7
9 2 4

Sample Output 2

0

Sample Input 3

15 167 924
122 122 111 85 97 108 115 82 84 82 105 103 113 102 135
116 122 110 106 71 85 70 94 86 110 73 97 101 86 73

Sample Output 3

9576277