AT_abc216_f [ABC216F] Max Sum Counting

[problemUrl]: https://atcoder.jp/contests/abc216/tasks/abc216_f 長さ $ 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 $ で割ったあまりを出力せよ。

### 制約 - $ 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 $ が存在しない場合もあります。