#include <stdio.h> #include <stdlib.h> #define N 4000 #include "string.h" #define INF 0x80000000 int max(int a,int b){ int i=a>b?a:b; return i; } int main() { int n,V,i,a[N],dp[N],b[N],j; scanf("%d %d",&n,&V); for(i=0;i<n;i++){ scanf("%d %d",&a[i],&b[i]); dp[i]=0; } for(i=1;i<=n;i++){ for(j=a[i-1];j<=V;j++){ dp[j]=max(dp[j-a[i-1]]+b[i-1],dp[j]); } } printf("%d\n",dp[V]); for(i=1;i<=V;i++){ dp[i]=INF; } for(i=1;i<=n;i++){ for(j=a[i-1];j<=V;j++){ dp[j]=max(dp[j],dp[j-a[i-1]]+b[i-1]); } } if(dp[V]>0) printf("%d",dp[V]); else printf("0"); }