\(max(A_{S})\) と \(sum(B_{S})\) をとる． \(A\) をソートしておくと良さそう，ただしそれに合わせて \(B\) も一緒にソートする． \(i \in N\) を全探索して， \(A_{i}\) が最大になる \(S\) の取り方を調べる． \(sum(B_{S}) \leq A_{i}\) になる様にすればよい． よって，以下のDPが良い．
\(dp[i][x] := [0,i)\) で見たときの， \(B\) の部分和で \(x\) 以下になるものの個数．
これは部分和DPとほぼ同じで，初期化が異なるだけ． \(dp[0][x] = 1\) , \(x \geq 0\) とすれば良い． 初期値 \(0\) から 和\(t\) を作るのと， 初期値 \(S-t\) から 和\(S\) を作るのは対応するから． ここで， \(0 \leq t \leq S\).
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n;
cin >> n;
rep(i,n){
cin >> p[i].first;
}
rep(i,n){
cin >> p[i].second;
}
sort(all(p));
const ll ma = 5000;
mint ans = 0;
rep(i,n){
auto [a,b] = p[i];
// dp: [0,i)
if(a >= b) ans += dp[a-b];
// ------------------------
drep(x,ma+1){
ll y = b + x;
if(y <= ma) dp[y] += dp[x];
}
// dp: [0,i]
}
cout << ans.val() << endl;
return 0;
}
