Sort the given two sequences \(A\) and \(B\) as a sequence of pair of elements in the increasing order of \(A_i\) (with ties broken properly, like by comparing \(B_i\)). Then, for every non-empty subset \(S\) of \(\{1,2,\ldots,N\}\), it holds that \(\max_{i \in S} A_i=A_{\max(S)}\), so we can transform the problem as follows.

Let us define \(f(i,j)\) as the number of ways to choosing zero or more elements from \((B_1,B_2,\ldots,B_i\) so that their sum is equal to \(j\). Find the following value.

• \(\sum_{i=1}^{N} \sum_{j=0}^{A_i-B_i} f(i-1,j)\)

Obviously, for \(f(i,j)\), we may only consider the domain of \(i\) between \(0\) and \(N\) (inclusive), and the domain of \(j\) between \(0\) and \(\max(A)\) (inclusive). Therefore, we may use DP (Dynamic Programming) properly to find the values of \(f(i, j)\) so that the problem is solved in a total of \(O(N \max(A))\) time.

Sample code (C++)

#include<bits/stdc++.h>
using namespace std;

const int mod = 998244353, maxi = 5000;

int main(){
	int N; cin >> N;
	vector<pair<int,int>> data(N);
	for(int i=0; i<N; i++) cin >> data[i].first;
	for(int i=0; i<N; i++) cin >> data[i].second;
	sort(data.begin(),data.end());
	vector<int> A(N),B(N);
	for(int i=0; i<N; i++) tie(A[i],B[i]) = data[i];
	vector<vector<int>> dp(N+1,vector<int>(maxi+1));
	dp[0][0] = 1;
	int ans = 0;
	for(int i=0; i<N; i++){
		for(int j=0; j<=maxi; j++){
			dp[i+1][j] = dp[i][j];
			if(B[i] <= j){
				dp[i+1][j] += dp[i][j-B[i]];
				dp[i+1][j] %= mod;
			}
			if(j <= A[i]-B[i]){
				ans += dp[i][j];
				ans %= mod;
			}
		}
	}
	cout << ans << endl;
}