#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long BITMASK;
#define int long long
#define double long double
#define flash ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MAXN 105
#define MAXM 45
#define MAXK 100005
#define CLOCK_START clock_t chrono_clk_beg = clock()
#define CLOCK_END clock_t chrono_clk_end = clock(); cerr << (double(chrono_clk_end - chrono_clk_beg) / CLOCKS_PER_SEC) << " sec"
#define mat(x, y, name) vector< vector<int> > name (x, vector<int>(y));
#define printMat(name) for (int i = 0; i < name.size(); ++i) {for (int j = 0; j < name[i].size(); ++j) cout << name[i][j] << " "; cout << endl;}
#define printArr(name) for (int i : name) cout << i << " "; cout << '\n'
#define printArr1(name) for (int i = 1; i < name.size(); ++i) cout << name[i] << " "; cout << '\n'
#define removeDup(name) sort(name.begin(), name.end()); name.erase(unique(name.begin(), name.end()), name.end())
#define minheap(name) priority_queue <int, vector<int>, greater<int> > name;
#define fractional(name) (name - floor(name))
#define CONST_E 2.71828182845904523536
#define CONST_PI 3.141592653589793238461
#define has_bit(bit_mask, x) ((bit_mask) & (1ULL << (x)))
#define turn_on_bit(bit_mask, x) (bit_mask |= (1ULL << (x)))
#define turn_off_bit(bit_mask, x) (bit_mask &= (~(1ULL << (x))))
#define smallest_on_bit(bit_mask) (__builtin_ctzll((bit_mask) & (-(bit_mask))))
const int M = 1e9 + 7;
// vector<int> adj[MAXN]; unordered_set<int> adj2[MAXN]; vector<int> deg(MAXN, 0); vector<bool> visited(MAXN, false); unordered_set<int> visited2; vector< pair<int, int> > adjW[MAXN];
// #define INP_GRAPH { int x, y; cin >> x >> y; x--, y--; adj2[x].insert(y); adj2[y].insert(x); adj[x].push_back(y); adj[y].push_back(x); deg[x]++, deg[y]++; }
// #define INP_GRAPH_WEIGHT { int x, y, w; cin >> x >> y >> w; x--, y--; adjW[x].push_back({y, w}); adjW[y].push_back({x, w}); deg[x]++, deg[y]++; }
int powMod(int a, int b, int m) { int x = 1; while (b > 0) { if (b&1) x = (x*a) % m; a = (a*a) % m; b >>= 1;} return x; }
int mulMod(int a, int b, int m) { int res = 0; a = a % m; while (b > 0) { if (b % 2 == 1) res = (res + a) % m; a = (a * 2) % m; b /= 2; } return res % m; }
int nCr(int n, int r, int m) { if (n < r) return 0; int res = 1, rem = 1; for (int i = n - r + 1; i <= n; i++) res = (res * i) % m; for (int i = 2; i <= r; i++) rem = (rem * i) % m; return (res * powMod(rem, m - 2, m)) % m; }
int modInverse(int a, int m) { a = a % m; for (int x = 1; x < m; ++x) { if ((a * x) % m == 1) return x; } return -1; }
int gcdExtended(int a, int b, int *x, int *y) { if (b == 0) { *x = 1, *y = 0; return a; } int x1, y1; int gcd = gcdExtended(b, a%b, &x1, &y1); *x = y1, *y = x1 - (floor(a/b) * y1); return gcd; }
int factorial(int n) { if (n == 1) return 1; return sqrt(2 * CONST_PI * n) * pow((n / CONST_E), n); }
vector<bool> sieve(int n) { int sqrtn = sqrt(n); vector<bool> is_prime(n+1, true); for (int i = 3; i <= sqrtn; i += 2) { if (is_prime[i]) { int increment = i+i; for (int j = i * i; j <= n; j += increment) is_prime[j] = false; } } return is_prime; }
vector<pair<int, int>> primeFactors(int n) { vector<pair<int, int>> ans; for (int i = 2; i * i <= n; ++i) { if (n % i == 0) { int cnt = 0; while (n % i == 0) n /= i, cnt++; if (cnt) ans.push_back({i, cnt}); } } if (n > 1) ans.push_back({n, 1}); return ans; }
void factors(vector< pair<int, int> > primeFactors, vector<int> &ans, int cur = 0, int curRes = 1) { if (cur == primeFactors.size()) { ans.push_back(curRes); return; } for (int i = 0; i <= primeFactors[cur].second; ++i) { factors(primeFactors, ans, cur+1, curRes); curRes *= primeFactors[cur].first; } }
vector< vector<int> > matMul(vector< vector<int> > A, vector< vector<int> > B) { vector< vector<int> > C(A.size(), vector<int>(B[0].size())); for (int i = 0; i < A.size(); ++i) { for (int j = 0; j < B[0].size(); ++j) { C[i][j] = 0; for (int k = 0; k < B.size(); ++k) C[i][j] = (C[i][j] + ((A[i][k] * B[k][j]) % M)) % M; } } return C; }
vector< vector<int> > matPow(vector< vector<int> > A, int p) { if (p == 1) return A; if (p&1) return matMul(A, matPow(A, p-1)); else { vector< vector<int> > C = matPow(A, p/2); return matMul(C, C); } }
vector<int> zFunction(string s) { int n = s.size(), L = 0, R = 0; vector<int> z(n); for (int i = 1; i < n; ++i) { if (i > R) { L = R = i; while (R < n && s[R - L] == s[R]) R++; z[i] = R - L; R--; } else { int k = i - L; if (z[k] < R - i + 1) z[i] = z[k]; else { L = i; while (R < n && s[R - L] == s[R]) R++; z[i] = R - L; R--; } } } return z; }
vector<int> patterMatch(string text, string pattern) { string key = pattern + '$' + text; vector<int> z = zFunction(key); vector<int> res; int m = pattern.size(); for (int i = m+1; i < key.size(); ++i) if (z[i] == m) res.push_back(i-m-1); return res; }
vector<int> kaden(vector<int> &arr) { vector<int> kaden(arr.size()); kaden[0] = arr[0]; for (int i = 1; i < arr.size(); ++i) kaden[i] = max(arr[i], arr[i] + kaden[i-1]); return kaden; }
// int fact[MAXN], inv[MAXN];
// void nCrPreProcess() { fact[0] = inv[0] = 1; for(int i = 1; i < MAXN; ++i) { fact[i] = (fact[i-1] * i) % M; inv[i] = powMod(fact[i], M-2, M); } }
// int nCrQuery(int n, int r, int M) { int res = 1; res = (res * 1ll * fact[n]) % M; res = (res * 1ll * inv[r]) % M; res = (res * 1ll * inv[n-r]) % M; return res; }
int digitSum(int x) { int ds = 0; while(x) { ds += x%10; x /= 10; } return ds; }
//////////////////////////////////// CODE BEGINS HERE ////////////////////////////////////

signed main()
{
    flash;

    int n, c;
    cin >> n >> c;
    vector< pair<int, int> > arr(n+1);
    for (int i = 1; i <= n; ++i) cin >> arr[i].first >> arr[i].second;
    vector< vector<int> > DP(n+1, vector<int>(c+1, 0));
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= c; ++j)
            DP[i][j] = (j < arr[i].first) ? DP[i-1][j] :
                max(DP[i-1][j], arr[i].second + DP[i-1][j - arr[i].first]);
    }
    cout << DP[n][c] << '\n';
    return 0;
}

Measured memory_bytes: 80256