//朴适做法
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();//物品
int V = sc.nextInt();//容量
int[] vi = new int[N+1];
int[] wi = new int[N+1];
int[][] pagk = new int[N+1][V+1];
for(int i=1;i<=N;i++){
wi[i]=sc.nextInt();
vi[i]=sc.nextInt();
}
pagk[0][0]=0;
for(int i=1;i<=N;i++){
for(int j=0;j<=V;j++){
pagk[i][j]=pagk[i-1][j];
if(j>=wi[i]) pagk[i][j]=Math.max(pagk[i-1][j],pagk[i-1][j-wi[i]]+vi[i]);
}
}
System.out.println(pagk[N][V]);
}
}
//滚筒法
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int N=sc.nextInt();
int V=sc.nextInt();
int[] pagk = new int[V+1];
int[] vi = new int[N+1];
int[] wi = new int[N+1];
for(int i=1;i<=N;i++){
wi[i]=sc.nextInt();
vi[i]=sc.nextInt();
}
for(int i=1;i<=N;i++){
for(int j=V;j>=wi[i];j--){
if(j>=wi[i])
pagk[j]=Math.max(pagk[j],pagk[j-wi[i]]+vi[i]);
}
}
System.out.println(pagk[V]);
}
}