//朴素二维

#include <iostream>

#include <algorithm>

using namespace std;

const int N = ;

int n, m;

int v[N], w[N];

int f[N][N];

int main() {

    cin >> n >> m;

    for (int i = ; i <= n; i ++ )

        cin >> v[i] >> w[i];

    for(int i=; i<=n; i++)//装的个数

        for(int j=; j<=m; j++) {//最大容量

        //讲 f[i][j]分为f[i-1][j](去掉第i个)和 f[i-1][j-v[i]]+w[i](先去掉第i个,并减去他的质量,再加上)

            f[i][j]=f[i-][j];//左边

            //右边

            //当j<v[i]时,情况不存在,就不用考虑

            if(j>=v[i]) f[i][j]=max(f[i][j],f[i-][j-v[i]]+w[i]);

        }

    cout<<f[n][m]<<endl;

    return ;

}

//一维优化

#include <iostream>

#include <algorithm>

using namespace std;

const int N = ;

int n, m;

int v[N], w[N];

int f[N];

int main() {

    cin >> m >> n;//m表示时间,n表示数量

    for (int i = ; i <= n; i ++ ) cin >> v[i] >> w[i];

    for (int i = ; i <= n; i ++ )

        for (int j = m; j >= v[i]; j -- )

            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m];

    return ;

}