まず、\(A\) と \(B\) を セットにして、\(A\) の昇順にソートしておきます。

また、\(\{1,2,\ldots,i\}\) の部分集合(空集合も含む)を \(S_i\) とします。

---

\[F(i, j) =(j \ge \sum_{k \in S_i} B_k となるS_{i}の数)\]

という関数を考えます。

DPパート

上記の関数 \(F\) は簡単な動的計画法で解けます。

公式解説にもあるとおり、 \(\sum_{k \in S_i} B_k \) が \(\max (A)\) を超える場合を考える必要はないので、\(j \le \max (A)\) として良いです。

\(i=0\) のとき

\(S_0\) としてありえるのは空集合 \(\emptyset\) だけです。

\(\sum_{k \in \emptyset} B_k=0\) より

\[ \left\{ \begin{array}{ll} F(0, j) = 1 & j \ge 0 \\ F(0, j) = 0 & j \lt 0 \end{array} \right. \]

となります。

\(i>0\) のとき

\[F(i, j) =F(i-1, j) +F(i-1, j-B_i)\]

です。

これは、

\((B_i を採用しない場合の数)+(B_i を採用する場合の数)\)

を表します。

合計パート

\(A\) がソート済みなので

\[\max_{i \in S} A_i = A_{\max i \in S}\]

です。

つまり、\(S\) に含まれる最大値が \(k\) のとき \(A_k \ge \sum_{i \in S} B_i\) をみたすものを数え上げればよいです。

このとき、

\[\sum_{i \in S} B_i = B_k + \sum_{i \in S_{k-1}} B_i\]

となります。

よって、

\[A_k - B_k \ge \sum_{i \in S_{k-1}} B_i\]

をみたすものの数を数え上げればよいです。

これは \(F(k-1, A_k - B_k )\) で取得できます。

求める答えは

\[\sum_{k=1}^N F(k-1, A_k - B_k )\]

となります。

提出例(C#): https://atcoder.jp/contests/abc216/submissions/29591012