import java.util.*;
class Main{
public static void main(String[] args){
Scanner kb = new Scanner(System.in);
int n=kb.nextInt(); // 문제 개수
int m=kb.nextInt(); // 총 시간
int[] dy=new int[m+1];
for(int i=0; i<n; i++){
int ps=kb.nextInt(); // 문제의 점수
int pt=kb.nextInt(); // 문제의 시간
for(int j=m; j>=pt; j--){ // 문제를 풀어서 점수를 획득한 시간부터 총시간까지
dy[j]=Math.max(dy[j], dy[j-pt]+ps); // 기존의 최대 점수와 현재 문제를 풀었을 때 점수를 비교한다.
}
}
System.out.print(dy[m]);
}
}
▣ 입력예제 1 5 20 10 5 25 12 15 8 6 3 7 4
▣ 출력예제 1 41