题目描述

長さ $N$ の数列 $ A\ =\ (A_1,\ \dots,\ A_N),\ B\ =\ (B_1,\ \dots,\ B_N) $ が与えられます。$\{1,2,\ldots,N\}$ の空でない部分集合 $S$ であって、以下の条件を満たすものの個数を数えてください。

• $ \max_{i\ \in\ S}\ A_i\ \geq\ \sum_{i\ \in\ S}\ B_i $

なお、答えは非常に大きくなることがあるため、$998244353$ で割ったあまりを出力してください。

输入格式

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

$N$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_N$

输出格式

問題文中の条件を満たす $S$ の個数を $998244353$ で割ったあまりを出力せよ。

题目大意

给出两个有 $n$ 个元素的序列 $a,b$，现在在 $1 - n$ 中选一些数构成集合 $S$，使得 $max_{i \in S} \space a_i \ge \sum_{i \in S} \space b_i$，问合法的集合 $S$ 的个数 $\mod 998244353$。 $1 \le N \le 5000,1 \le a_i,b_i \le 5000$.

2
3 1
1 2

2

2
1 1
2 2

0

20
1937 3980 2689 1208 3640 1979 581 2271 4229 3948 3708 1522 4161 4661 3797 96 3388 3395 2920 2247
4485 2580 174 1156 3770 3396 3558 3500 3494 479 269 3383 1230 1711 3545 3919 134 475 3796 1017

476

提示

制約

• $1\ \leq\ N\ \leq\ 5000$
• $1\ \leq\ A_i,B_i\ \leq\ 5000$
• 入力は全て整数

Sample Explanation 1

$\{1,2,\ldots,N\}$ の空でない部分集合としてあり得るものは、$\{1\}$, $\{2\}$, $\{1,2\}$ の $3$ 通りです。 - $S=\{1\}$ のとき $\max_{i\ \in\ S}\ A_i=3$, $\sum_{i\ \in\ S}\ B_i=1$ - $S=\{2\}$ のとき $\max_{i\ \in\ S}\ A_i=1$, $\sum_{i\ \in\ S}\ B_i=2$ - $S=\{1,2\}$ のとき $\max_{i\ \in\ S}\ A_i=3$, $\sum_{i\ \in\ S}\ B_i=3$ であるため、問題文中の条件、即ち $ \max_{i\ \in\ S}\ A_i\ \geq\ \sum_{i\ \in\ S}\ B_i $ を満たす $S$ は $\{1\}$ と $\{1,2\}$ の $2$ 通りです。

Sample Explanation 2

条件を満たす $S$ が存在しない場合もあります。