Scanner s=new Scanner(System.in);
int n=s.nextInt();//数量
int v=s.nextInt();//容积
int vi[]=new int[n+1];//体积
int wi[]=new int[n+1];//价值
for(int i=1;i<=n;i++) {//输入体积 价值。
vi[i]=s.nextInt();//表示第i个物品体积
wi[i]=s.nextInt();//表示第i个物品价值
}s.close();
int dp[][]=new int[n+1][v+1];
//dp[i][j]表示前i个物品,容量为j情况下的最大价值。
//初始化
dp[0][0]=0;
//核心代码
for(int i=1;i<=n;i++) {
for(int j=0;j<=v;j++) {
if(j>=vi[i]) {//容量大于第i个物品体积,还能装。
dp[i][j]=Math.max(dp[i-1][j], wi[i]+dp[i-1][j-vi[i]]);
}else {//小于.....
dp[i][j]=dp[i-1][j];
}
}
}
System.out.println(dp[n][v]);