LUCKUST

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 1e3+5;
int n, m, t;
int r[N], l[N], v[N], w[N];
int dp[N][N], res[N];
void dac(int lef, int rig, vector<int>& q) {
    if(lef > rig)return;
    if(lef == rig){
        for(int i: q){
            res[i] = (w[lef] <= m ? v[lef] : 0);
        }
        return;
    }
    int mid = (lef+rig)/2;
    for(int i = 0; i <= m; i ++){
        if(i >= w[mid])dp[mid][i] = v[mid];
        else dp[mid][i] = 0;
        if(i >= w[mid+1])dp[mid+1][i] = v[mid+1];
        else dp[mid+1][i] = 0;
    }
    for(int i = mid-1; i >= lef; i --){
        for(int j = m; j >= 0; j --){
            dp[i][j] = dp[i+1][j];
            if(j >= w[i])dp[i][j] = max(dp[i][j], dp[i+1][j-w[i]]+v[i]);
        }
    }
    for(int i = mid+2; i <= rig; i ++){
        for(int j = m; j >= 0; j --){
            dp[i][j] = dp[i-1][j];
            if(j >= w[i])dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]]+v[i]);
        }
    }
    vector<int> vl, vr;
    while(!q.empty()){
        int i = q.back();
        q.pop_back();
        if(l[i] <= mid && mid <= r[i]){
            if(r[i] == mid)res[i] = dp[l[i]][m];
            else{
                for(int j = 0; j <= m; j ++){
                    res[i] = max(res[i], dp[l[i]][j]+dp[r[i]][m-j]);
                }
            }
        }
        else if(r[i] <= mid)vl.pb(i);
        else vr.pb(i);
    }
    dac(lef, mid, vl);
    dac(mid+1, rig, vr);
}
int main() {
     #define task "test"
    if(fopen(task".inp", "r"))
    {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)cin >> w[i] >> v[i];
    cin >> t;
    vector<int> q;
    for(int i = 1; i <= t; i ++){
        cin >> l[i] >> r[i];
        q.pb(i);
    }
    dac(1, n, q);
    for(int i = 1; i <= t; i ++)cout << res[i] << '\n';
}