0-1 Knapsac(DP)

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
const ll mx=100001;

ll cost[mx],weight[mx];
ll n,cap;

ll func(ll i, ll w)
{
    ll profit1,profit2;
    if(i==n)
        return 0;
    if(w+weight[i]<=cap)
        profit1=cost[i]+func(i+1,w+weight[i]);
    else
        profit1=0;
    profit2=func(i+1,w);

    return max(profit1,profit2);
}



int main()
{
    cin>>n>>cap;

    for(int i=0; i<n; i++)
        cin>>weight[i]>>cost[i];

    cout<<func(0,0)<<endl;

    return 0;
}