include [HTML_REMOVED]

include [HTML_REMOVED]

int main ()
{
int n, m, dp[1005];
int v[1005], w[1005];
while (~scanf (“%d%d”, &n, &m))
{
for (int i = 0; i < n; i)
scanf (“%d%d”, &v[i], &w[i]);
memset(dp, 0, sizeof(dp));
for (int j = 0; j < n; j)
{
for (int i = m; i >= 0; i–)
{
if (i >= v[j])
dp[i] = dp[i] > (dp[i-v[j]] + w[j]) ? dp[i] : (dp[i-v[j]] + w[j]);
}
}
printf (“%d\n”, dp[m]);
}
return 0;
}