> /**
>  * POJ probem 3624: 0/1 knapsack algorithm
>  * Basically, use brute force search method (dfs).
>  * A better way is to use DP.
>  *
>  * hellfire (asyncloading#163.com)
>  * Jan 31th, 2016
>  */
> 
> #include<iostream>
> 
> using namespace std;
> 
> int n;
> 
> int m;
> 
> int martix[12880][2];
> int mem[3402][12880];
> 
> int dfs(int i, int j)
> {
>   int res;
>   if (mem[i][j] >= 0)
>   {
>     return mem[i][j];
>   }
>   if (i == n)
>   {
>     res = 0;
>   }
>   else if (martix[i][0] > j )
>   {
>     res = dfs(i + 1, j);
>   }
>   else 
>   {
>     res = max(dfs(i + 1, j), dfs(i + 1, j - martix[i][0]) + martix[i][1]);
>   }
>   return mem[i][j] = res;
> }
> 
> int main(int argc, char **argv)
> {
>   cin >> n >> m;
>   int k;
>   for (k = 0; k < n; k ++)
>   {
>     cin >> martix[k][0] >> martix[k][1];
>   }
>   memset(mem, -1, sizeof(mem));
>   int result = dfs(0, m);
>   cout << result << endl;
> }