stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;

using ll = long long;



ll Sum(ll n) { return (n * (n + 1) / 2) % 1000000007; }



struct ModComb {

	vector<long long> fac;

	vector<long long> ifac;

	const long long MOD = 1000000007;



	template <typename T>

	T power(T a, T b) {

		T ret = 1;

		while (b > 0) {

			if (b&1) { (ret *= a) %= MOD; }

			(a *= a) %= MOD;

			b >>= 1;

		}

		return ret;

	}



	ModComb(const size_t SIZE) {

		fac.assign(SIZE, 0);

		ifac.assign(SIZE, 0);



		fac[0] = ifac[0] = 1;

		for (int i = 1; i < SIZE; ++i) {

			fac[i] = (fac[i - 1] * i) % MOD;

			ifac[i] = power(fac[i], MOD - 2) % MOD;

		}

	}



	long long nCr(size_t n, size_t r) {

		return (((fac[n] * ifac[r]) % MOD) * ifac[n - r]) % MOD;

	}

};



int main() {

	const ll MOD = 1e9 + 7;

	ll N, M, K;

	cin >> N >> M >> K;



	ModComb comb(N * M + 1);

	ll C, res = 0;

	if (N * M == 2 || K == 2) { C = 1; }

	else { C = comb.nCr(N * M - 2, K - 2); }

	for (int i = 0; i < N; ++i) {

		for (int j = 0; j < M; ++j) {

			ll cost = (Sum(N - i - 1) * M + Sum(j) * (N - i - 1) + Sum(M - j - 1) * (N - i)) % MOD;

			(res += (cost * C) % MOD) %= MOD;

		}

	}



	cout << res % MOD << endl;



	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 4.884121584994417x):
#include <bits/stdc++.h>



using namespace std;

using ll = long long;



struct Combination {

    vector<int64_t> fact, rfact;

	const int64_t MOD = 1000000007;



    Combination(int sz) : fact(sz + 1), rfact(sz + 1) {

        fact[0] = 1;

        for(int i = 1; i < fact.size(); i++){

            fact[i] = fact[i - 1] * i % MOD;

        }

        rfact[sz] = inv(fact[sz]);

        for(int i = sz - 1; i >= 0; i--){

            rfact[i] = rfact[i + 1] * (i + 1) % MOD;

        }

    }

    int64_t inv(int x) const {

        return pow(x, MOD - 2);

    }

    int64_t pow(int64_t x, int64_t n) const {

        int64_t ret = 1;

        while (n > 0) {

            if (n & 1) { (ret *= x) %= MOD; }

            (x *= x) %= MOD;

            n >>= 1;

        }

        return (ret);

    }



    int64_t P(int n, int r) const {

        if (r < 0 || n < r) { return 0; }

        return (fact[n] * rfact[n - r] % MOD);

    }



    int64_t C(int p, int q) const {

        if (q < 0 || p < q) { return 0; }

        return (fact[p] * rfact[q] % MOD * rfact[p - q] % MOD);

    }



    int64_t H(int n, int r) const {

        if (n < 0 || r < 0) { return 0; }

        return (r == 0 ? 1 : C(n + r - 1, r));

    }

};



ll calc(ll n) { return (n * (n + 1) / 2) % 1000000007; }



int main() {

	const ll MOD = 1e9 + 7;

	ll N, M, K;

	cin >> N >> M >> K;



	Combination comb(N * M);

	ll res = 0;

	for (int i = 0; i < N; ++i) {

		for (int j = 0; j < M; ++j) {

			ll cost = (calc(N - i - 1) * M + calc(j) * (N - i - 1) + calc(M - j - 1) * (N - i)) % MOD;

			(res += (cost * comb.C(N * M - 2, K - 2)) % MOD) %= MOD;

		}

	}

	cout << res % MOD << endl;



	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

typedef long long ll;

typedef long double ld;

using namespace std;



int main(){

    int N, T;  cin >> N >> T;

    vector<pair<int, int>> D(N);

    for(int i=0; i<N; i++){

        cin >> D[i].first >> D[i].second;

    }

    sort(D.begin(), D.end(),[](const pair<int,int>& a, const pair<int,int>& b){

        return a.second < b.second;

    });

    vector<pair<int,int>> E(N);

    for(int i=0; i<N; i++){

        E[i] = D[N-1-i];

    }



    int maxT = T + 3000;

    vector<vector<int>> dp1(N+1, vector<int>(maxT + 1, 0));

    vector<vector<int>> dp2(N+1, vector<int>(maxT + 1, 0));

    for(int i=0; i<N; i++) for(int j=0; j<=maxT; j++){

        dp1[i+1][j] = dp1[i][j];

        dp2[i+1][j] = dp2[i][j];

        if(j >= D[i].first){

            dp1[i+1][j] = max(dp1[i+1][j], dp1[i][j-D[i].first]+D[i].second);

        }



        if(j >= E[i].first){

            dp2[i+1][j] = max(dp2[i+1][j], dp2[i][j-E[i].first]+E[i].second);

        }

    }



    int ans = 0;

    for(int i=0; i<N; i++) for(int j=0; j<=T-1; j++){

        ans = max(ans, dp1[i][j] + dp2[N-i-1][T-j-1] + D[i].second);

    }

    cout << ans << endl;

}   

// Faster C++ solution for the same problem (measured speedup: 1.4956524935106676x):
#include <bits/stdc++.h>

#define ll long long

#define ld long double

using namespace std;



int main() {

    int N, T;

    cin >> N >> T;

    vector<pair<int, int>> D(N);

    for (int i = 0; i < N; i++) {

        cin >> D[i].first >> D[i].second;

    }

    sort(D.begin(), D.end());



    vector<vector<int>> dp(N, vector<int>(T, 0));

    if (D[0].first < T) {

        dp[0][D[0].first] = D[0].second;

    }

    for (int i = 1; i < N; i++) {

        for (int t = 0; t < T; t++) {

            dp[i][t] = dp[i - 1][t];

            if (D[i].first <= t) {

                dp[i][t] = max(dp[i][t], dp[i - 1][t - D[i].first] + D[i].second);

            }

        }

    }



    int ans = 0;

    for (int i = 0; i < N; i++) {

        int temp = 0;

        for (int t = 0; t < T; t++) {

            temp = max(temp, dp[i][t]);

        }

        if (i != N - 1) {

            temp += D[i + 1].second;

        }

        ans = max(ans, temp);

    }

    cout << ans << endl;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> P;

#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)

#define chmax(x,y) x=max(x,y)

const int mod = 1000000007;



int main() {

  int n, t;

  cin >> n >> t;

  vector<P> p(n);

  rep(i, n) cin >> p[i].first >> p[i].second;

  vector<vector<int>> dp(n + 1, vector<int>(3010));

  sort(p.begin(), p.end());

  int ans = 0;

  rep(i, n) {

    rep(j, t) {

      chmax(dp[i + 1][j], dp[i][j]);

      int nj = j + p[i].first;

      if(nj < t) chmax(dp[i + 1][nj], dp[i][j] + p[i].second);

    }

    chmax(ans, dp[i][t - 1] + p[i].second);

  }

  cout << ans << endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.205850475495805x):
#include<iostream>

#include<vector>

#include<string>

#include<algorithm>

#include<utility>

#include<cmath>

#include<climits>

#include<queue>

#include<stack>

#include<numeric>

#include<set>

#include<iomanip>

#include<map>

#include<type_traits>

#include<tuple>

#include<deque>

#include<cassert>

#include<bitset>

using namespace std;

typedef long long ll;

typedef pair<int,int> P;

#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)

#define chmax(x,y) x=max(x,y)

#define chmin(x,y) x=min(x,y)

const int mod = 1000000007;

const int MAXV =  3010;



int dp[MAXV][MAXV];



int main() {

  int n, t;

  cin >> n >> t;

  vector<pair<int, int>> p(n);

  rep(i, n) cin >> p[i].first >> p[i].second;

  sort(p.begin(), p.end());

  int ans = 0;

  rep(i, n) {

    rep(j, t) {

      chmax(dp[i + 1][j], dp[i][j]);

      int nj = p[i].first + j;

      if (nj < t) chmax(dp[i + 1][nj], dp[i][j] + p[i].second);

    }

    chmax(ans, dp[i][t - 1] + p[i].second);



  }

  cout << ans << endl;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define FOR(i,l,r) for(long long i=(l);i<(r);++i)

#define REP(i,n) FOR(i,0,n)

#define REPS(i,n) FOR(i,1,n+1)

#define RFOR(i,l,r) for(long long i=(l);i>=(r);--i)

#define RREP(i,n) RFOR(i,N-1,0)

#define RREPS(i,n) RFOR(i,N,1)

#define int long long

#define mp make_pair

#define pb push_back

#define eb emplace_back

#define SZ(x) ((int)(x).size())

#define all(x) (x).begin(),(x).end()

template<class T> inline bool chmin(T& a, T b) {

    if (a > b) {

        a = b;

        return true;

    }

    return false;

}

template<class T> inline bool chmax(T& a, T b) {

    if (a < b) {

        a = b;

        return true;

    }

    return false;

}

const int INF=1e18;

const int MOD=1e9+7;



signed main(){

    int N,T;cin>>N>>T;

    vector<pair<int,int>>vec(N);

    REP(i,N){

        int a,b;cin>>a>>b;

        vec[i]={a,b};

    }

    sort(all(vec));

    int dp[N+1][T+3000];

  	REP(i,N+1)REP(j,T+3000)dp[i][j]=0;

    REP(i,N){

        REP(j,T){

            chmax(dp[i+1][j+vec[i].first],dp[i][j]+vec[i].second);

            chmax(dp[i+1][j],dp[i][j]);

        }

    }

    int ans=0;

    REP(i,N+1)REP(j,T+3000)chmax(ans,dp[i][j]);

    cout<<ans<<endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.1495896749307453x):
#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define FOR(i,l,r) for(ll i=(l);i<(r);++i)

#define REP(i,n) FOR(i,0,n)

#define REPS(i,n) FOR(i,1,n+1)

#define RFOR(i,l,r) for(ll i=(l);i>=(r);--i)

#define RREP(i,n) RFOR(i,n-1,0)

#define RREPS(i,n) RFOR(i,n,1)

#define pb push_back

#define eb emplace_back

#define SZ(x) ((ll)(x).size())

#define all(x) (x).begin(),(x).end()

#define rall(x) (x).rbegin(),(x).rend()

template<class T = ll> using V = vector<T>;

template<class T = ll> using VV = V<V<T>>;

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true; }return false; }

template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true; }return false; }

inline void Yes(bool b = true) {cout << (b ? "Yes" : "No") << '\n';}

inline void YES(bool b = true) {cout << (b ? "YES" : "NO") << '\n';}

inline void err(bool b = true) {if(b) {cout << -1 << '\n'; exit(0);}}

template<class T> inline void fin(bool b = true, T e = 0) {if(b) {cout << e << '\n'; exit(0);}}

template<class T> T Roundup_div(T x, T y) {return (x+(y-1))/y;}

const ll INF = 1e18;

template <typename T>

T pow(T a, long long n, T e = 1) {

    T ret = e;

    while (n) {

        if (n & 1) ret *= a;

        a *= a;

        n >>= 1;

    }

    return ret;

}



int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    ll n, t; cin >> n >> t;

    V<pair<ll,ll>> v(n);

    REP(i, n){

        ll a, b; cin >> a >> b;

        v[i] = {a, b};

    }

    sort(all(v));

    ll res = 0;

    V<> dp(t + 5000, 0);

    REP(i, n) RREP(j, t) chmax(dp[j+v[i].first], dp[j] + v[i].second);

    REP(j, t + 5000) chmax(res, dp[j]);

    cout << res << '\n';

}
// Slower C++ solution:
#include <iostream>

#include <limits>

#include <cfenv>

#include <cmath>

#include <algorithm>

#include <array>

#include <bitset>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#include <tuple>

#include <queue>

#include <vector>

#include <cmath>

#include <random>

#include <math.h>

#include <list>

#include <random>

#include <functional>





#define FOR(i, a, b) for(int (i) = (a); (i) < (b); ++(i))

#define REP(i, n) FOR(i, 0, n)

#define rREP(i, n) for(int (i) = (n) - 1; (i) >= 0; --(i))

#define ALL(TheArray) TheArray.begin(), TheArray.end()



using lli = long long int;

using pii = std::pair<int, int>;



template <class T> inline bool chmax(T& a, T b){

    if(a < b){a = b; return true;}

    return false;

}

template <class T> inline bool chmin(T& a, T b){

    if(a > b){a = b; return true;}

    return false;

}







// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~









// D[i] = 最初の注文からi分終了時で得られる最大の満足

constexpr int N = 3000;

std::array<lli, 2 * N + 1> D;

std::vector<std::pair<int, int>> A;

std::vector<bool> S;











int main(void){

    int n, t; scanf("%d%d", &n, &t);

    A.resize(n); REP(i, n) scanf("%d%d", &A[i].first, &A[i].second);

    std::sort(A.begin(), A.end());

    REP(i, n){

        int x = A[i].first, y = A[i].second;

        for(int j = t - 1; j >= 0; --j){

            if(D[j + x] < D[j] + y) D[j + x] = D[j] + y;

        }

    }

    lli res = 0;

    for(lli p : D) if(res < p) res = p;

    printf("%lld\n", res);

    

    return 0;

}




// Faster C++ solution for the same problem (measured speedup: 5.204256291802026x):
#include <stdio.h>

#include <array>

#include <algorithm>

#include <tuple>

 

#define FOR(i, a, b) for(int (i) = (a); (i) < (b); ++(i))

#define REP(i, n) FOR(i, 0, n)

 

using lli = long long int;



constexpr int N = 3000;

std::pair<int, int> A[N];

std::array<lli, N+1> R;



int main(void){

    int n, t; scanf("%d%d", &n, &t);

    REP(i, n) scanf("%d%d", &A[i].first, &A[i].second);

    std::sort(A, A+n);

    REP(i, n){

        int a = A[i].first, b = A[i].second;

        int j, e = (t > a) ? t - a : 0;

        for(j = t-1; j >= e; --j) if(R[t] < R[j] + b) R[t] = R[j] + b;

        for(; j >= 0; --j) if(R[j+a] < R[j] + b) R[j+a] = R[j] + b;

    }

    lli res = 0;

    for(int i = 0; i <= t; ++i) if(res < R[i]) res = R[i];

    printf("%lld\n", res);

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



using ll = long long;

using P = pair<ll, ll>;

using Graph = vector<vector<ll>>;

#define rep(i, n) for(ll i=0;i<(ll)(n);i++)

#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)

#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)

const int dx[4] = {1, 0, -1, 0};

const int dy[4] = {0, 1, 0, -1};

const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};

const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};

const ll MOD = 1000000007;

const ll INF = 1000000000000000000L;

#ifdef __DEBUG



/**

 * For DEBUG

 * https://github.com/ta7uw/cpp-pyprint

 */

#include "cpp-pyprint/pyprint.h"



#endif



void Main() {

    ll N, T;

    cin >> N >> T;

    vector<P> items(N);

    rep(i, N) cin >> items[i].first >> items[i].second;

    sort(items.begin(), items.end());

    vector<vector<ll>> dp(N + 1, vector<ll>(6005, 0));

    rep(i, N) {

        P p = items[i];

        rep(j, T + 3005) {

            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);

            if (j < T) {

                dp[i + 1][j + p.first] = max(dp[i + 1][j + p.first], dp[i][j] + p.second);

            }

        }

    }

    ll ans = 0;

    rep(i, 6005) {

        ans = max(ans, dp[N][i]);

    }

    cout << ans << '\n';

}



int main() {

    cin.tie(nullptr);

    ios::sync_with_stdio(false);

    cout << fixed << setprecision(15);

    Main();

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.2719042290249063x):
#include <bits/stdc++.h>



using namespace std;



using ll = long long;

using P = pair<ll, ll>;

using Graph = vector<vector<ll>>;

#define rep(i, n) for(ll i=0;i<(ll)(n);i++)

#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)

#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)

const int dx[4] = {1, 0, -1, 0};

const int dy[4] = {0, 1, 0, -1};

const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};

const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};

const ll MOD = 1000000007;

const ll INF = 1000000000000000000L;

#ifdef __DEBUG



/**

 * For DEBUG

 * https://github.com/ta7uw/cpp-pyprint

 */

#include "cpp-pyprint/pyprint.h"



#endif



void solve() {

    ll N, T;

    cin >> N >> T;

    vector<P> items(N);

    rep(i, N) cin >> items[i].first >> items[i].second;

    vector<vector<ll>> dp(N + 1, vector<ll>(T + 3005, 0));

    sort(items.begin(), items.end());

    rep(i, N) {

        P p = items[i];

        rep(j, T + 3004) {

            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);

            if (j < T) {

                dp[i + 1][j + p.first] = max(dp[i + 1][j + p.first], dp[i][j] + p.second);

            }

        }

    }

    ll ans = 0;

    rep2(i, T, T + 3004) {

        ans = max(ans, dp[N][i]);

    }

    cout << ans << '\n';

}



int main() {

    cin.tie(nullptr);

    ios::sync_with_stdio(false);

    cout << fixed << setprecision(15);

    solve();

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

template <class T> inline bool chmax(T &a, T b) {

    if(a < b) {

        a = b;

        return 1;

    }

    return 0;

}

template <class T> inline bool chmin(T &a, T b) {

    if(a > b) {

        a = b;

        return 1;

    }

    return 0;

}

typedef long long int ll;



#define ALL(v) (v).begin(), (v).end()

#define RALL(v) (v).rbegin(), (v).rend()

#define endl "\n"

const double EPS = 1e-7;

const int INF = 1 << 30;

const ll LLINF = 1LL << 60;

const double PI = acos(-1);

const int MOD = 1000000007;

const int dx[4] = {1, 0, -1, 0};

const int dy[4] = {0, 1, 0, -1};



//-------------------------------------



using P = pair<int, int>;



int dp[3010][6020];



int main() {

    cin.tie(0);

    ios::sync_with_stdio(false);

    int n, t;

    cin >> n >> t;

    vector<P> ab(n);

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

        cin >> ab[i].first >> ab[i].second;

    }

    sort(ALL(ab));



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

        for(int j = 0; j < 6020; j++) {

            if(j < t) {

                chmax(dp[i + 1][j + ab[i].first], dp[i][j] + ab[i].second);

            }

            chmax(dp[i + 1][j], dp[i][j]);

        }

    }

    int ans = -INF;

    for(int i = 0; i < 6020; i++) {

        chmax(ans, dp[n][i]);

    }

    cout << ans << endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.1794518824051274x):
#include <bits/stdc++.h>

using namespace std;

template <class T> inline bool chmax(T &a, T b) {

    if(a < b) {

        a = b;

        return 1;

    }

    return 0;

}

template <class T> inline bool chmin(T &a, T b) {

    if(a > b) {

        a = b;

        return 1;

    }

    return 0;

}

typedef long long int ll;



#define ALL(v) (v).begin(), (v).end()

#define RALL(v) (v).rbegin(), (v).rend()

#define endl "\n"

const double EPS = 1e-7;

const int INF = 1 << 30;

const ll LLINF = 1LL << 60;

const double PI = acos(-1);

const int MOD = 1000000007;

const int dx[4] = {1, 0, -1, 0};

const int dy[4] = {0, 1, 0, -1};



//-------------------------------------



int dp[3010][3010][2];



int main() {

    cin.tie(0);

    ios::sync_with_stdio(false);

    int n, t;

    cin >> n >> t;

    vector<int> a(n), b(n);

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

        cin >> a[i] >> b[i];

    }



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

        for(int j = 0; j < t; j++) {

            for(int k = 0; k < 2; k++) {

                if(j - a[i] >= 0) {

                    chmax(dp[i + 1][j][k], dp[i][j - a[i]][k] + b[i]);

                }

                chmax(dp[i + 1][j][k], dp[i][j][k]);

                // 最後に食べるとき

                if(k == 0) {

                    chmax(dp[i + 1][j][1], dp[i][j][k] + b[i]);

                }

            }

        }

    }



    int ans = 0;

    for(int j = 0; j < t; j++) {

        for(int k = 0; k < 2; k++) {

            chmax(ans, dp[n][j][k]);

        }

    }

    cout << ans << endl;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define repd(i,a,b) for (int i=(a);i<(b);i++)

#define rep(i,n) repd(i,0,n)

#define all(x) (x).begin(),(x).end()

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

typedef long long ll;

const long long INF = 1LL << 60;

typedef pair<int, int> P;

int main()

{

    int N, T;

    cin >> N >> T;



    vector<P> AB(N);

    rep(i, N) {

        int A, B;

        cin >> A >> B;

        AB[i] = {A, B};

    }



    sort(all(AB));



    vector<vector<int>> dp(N + 1, vector<int>(7000, -1));

    dp[0][0] = 0;



    rep(i, N) {

        rep(j, 7000) {

            if (dp[i][j] != -1) {

                if (j < T) chmax(dp[i + 1][j + AB[i].first], dp[i][j] + AB[i].second);

                chmax(dp[i + 1][j], dp[i][j]);

            }

        }

    }



    int ans = 0;

    rep(i, dp[N].size()) {

        chmax(ans, dp[N][i]);

    }



    cout << ans << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.5335608762264972x):
#include <bits/stdc++.h>

using namespace std;

#define repd(i,a,b) for (int i=(a);i<(b);i++)

#define rep(i,n) repd(i,0,n)

#define all(x) (x).begin(),(x).end()

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

typedef long long ll;

const long long INF = 1LL << 60;

typedef pair<int, int> P;

int main()

{

    int N, T;

    cin >> N >> T;

    vector<P> AB(N);

    rep(i, N) {

        int A, B;

        cin >> A >> B;

        AB[i] = {A, B};

    }



    sort(all(AB));



    vector<vector<ll>> dp(N + 1, vector<ll>(T + 1));



    rep(i, N) {

        rep(j, T) {

            chmax(dp[i + 1][j], dp[i][j]);

            chmax(dp[i + 1][min(T, j + AB[i].first)], dp[i][j] + AB[i].second);

        }

    }



    ll ans = 0;

    rep(i, N) {

        chmax(ans, dp[i + 1][T]);

    }

    cout << ans << endl;

    return 0;

}
// Slower C++ solution:
#include <cstdio>

#include <iostream>

#include <string>

#include <vector>

#include <sstream>

#include <map>

#include <set>

#include <queue>

#include <algorithm>

#include <cmath>

#include <cstring>

#include <typeinfo>

#include <numeric>

#include <functional>

#include <unordered_map>

#include <bitset>

#include <stack>

#include <assert.h>

#include <unordered_set>

#include <random>







using namespace std;

using ll = long long;

using ull = unsigned long long;



const ll INF = 1e18;

const ll MOD = 1e9 + 7;



#define REP(i, n) for(ll i = 0; i < n; i++)



































int main(){

    ll n, t;

    cin >> n >> t;

    vector<ll> a(n), b(n);

    REP(i, n){

        cin >> a[i] >> b[i];

    }

    

    vector<vector<ll>> dp1(n + 2, vector<ll>(6005));

    vector<vector<ll>> dp2(n + 2, vector<ll>(6005));

    REP(i, n){

        REP(j, t){

            dp1[i + 1][j] = max(dp1[i + 1][j], dp1[i][j]);

            dp1[i + 1][j + a[i]] = max(dp1[i + 1][j + a[i]], dp1[i][j] + b[i]);

        }

    }

    for(ll i = n - 1; i >= 0; i--){

        REP(j, t){

            dp2[i + 1][j] = max(dp2[i + 1][j], dp2[i + 2][j]);

            dp2[i + 1][j + a[i]] = max(dp2[i + 1][j + a[i]], dp2[i + 2][j] + b[i]);

        }

    }

    ll ans = 0;

    for(ll i = 1; i <= n; i++){

        REP(j, t){

            ans = max(ans, dp1[i - 1][j] + dp2[i + 1][t - 1 - j] + b[i - 1]);

        }

    }

    cout << ans << endl;

}

// Faster C++ solution for the same problem (measured speedup: 2.560475284026186x):
#include <cstdio>

#include <iostream>

#include <string>

#include <vector>

#include <sstream>

#include <map>

#include <set>

#include <queue>

#include <algorithm>

#include <cmath>

#include <cstring>

#include <typeinfo>

#include <numeric>

#include <functional>

#include <unordered_map>

#include <bitset>

#include <stack>

#include <assert.h>

#include <unordered_set>

#include <random>







using namespace std;

using ll = long long;

using ull = unsigned long long;



const ll INF = 1e18;

const ll MOD = 1e9 + 7;



#define REP(i, n) for(ll i = 0; i < n; i++)



































int main(){

    ll n, t;

    cin >> n >> t;

    vector<pair<ll, ll>> v(n);

    REP(i, n){

        cin >> v[i].first >> v[i].second;

    }

    sort(v.begin(), v.end());

    vector<ll> dp(t + 3000);

    REP(i, n){

        vector<ll> tmp(t + 3000);

        REP(j, t){

            tmp[j + v[i].first] = dp[j] + v[i].second;

        }

        REP(j, t + 3000){

            dp[j] = max(dp[j], tmp[j]);

        }

    }

    cout << *max_element(dp.begin(), dp.end()) << endl;

}