\(L_i,R_i\) の制約がない形であれば、以下の DP を行えばよいです。

• \(dp[x] = \{ x\) 円以下で得られる満足度の最大値 \(\}\)

\(L_i,R_i\) の制約がある場合も解法はそう変わらず、以下のように解けばよいです。

• \(l=1,2,\dots,N\) について、以下を繰り返す。
  • 何も商品が売られていない状態の DP テーブルを用意する。
  • \(r=l,l+1,\dots,N\) について、以下を繰り返す。
    • DP テーブルに対し、商品 \(r\) に関する遷移を行う。
    • 現在の DP テーブルは商品 \(l,l+1,\dots,r\) が売られている状態に対応するので、その状態で答えなければならないクエリに解答する。

本解法の時間計算量は \(O(N^2M+Q)\) で、実行時間制限に十分間に合います。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;
using pl=pair<ll,ll>;

int main(){
  ll N,M,Q;
  cin >> N >> M >> Q;
  vector<ll> H(N),V(N);
  for(ll i=0;i<N;i++){
    cin >> H[i] >> V[i];
  }
  vector<vector<vector<pl>>> qs(N,vector<vector<pl>>(N));
  for(ll i=0;i<Q;i++){
    ll L,R,X;
    cin >> L >> R >> X;
    L--; R--;
    qs[L][R].push_back({X,i});
  }
  vector<ll> res(Q);
  for(ll l=0;l<N;l++){
    vector<ll> dp(M+1,0);
    for(ll r=l;r<N;r++){
      for(ll i=M;i>=H[r];i--){
        dp[i]=max(dp[i],dp[i-H[r]]+V[r]);
      }
      for(auto &nx : qs[l][r]){
        res[nx.second]=dp[nx.first];
      }
    }
  }
  for(auto &nx : res){cout << nx << "\n";}
  return 0;
}