import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());

        int[] T = new int[N];
        int[] S = new int[N];
        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            T[i] = Integer.parseInt(st.nextToken());
            S[i] = Integer.parseInt(st.nextToken());
        }

        int[][] dp = new int[N+1][X+1];

        for (int i=0; i<N+1; i++) {
            Arrays.fill(dp[i], -1);
        }

        dp[0][X] = 0;
        
        for (int i=0; i<N; i++) {
            int t = T[i];
            int s = S[i];
            for (int j=0; j<X+1; j++) {
                
                if(dp[i][j] >=0) {
                    int nextHp = Math.min(X, j+R);
                    dp[i+1][nextHp] = Math.max(dp[i+1][nextHp], dp[i][j]);

                    if(j>=s) {
                        dp[i+1][j-s] = Math.max(dp[i+1][j-s], dp[i][j]+t);
                    }
                    
                } 
            }
        }

        int maxTraining = 0;
        for (int j=0; j<=X; j++) {
            if (dp[N][j] > maxTraining) {
                maxTraining = dp[N][j];
            }
        }
        System.out.println(maxTraining);
    }
}

Embed on website

To embed this project on your website, copy the following code and paste it into your website's HTML: