stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <iostream>

#include <cstdio>



using namespace std;



int main(void) {



    int n;

    cin >> n;



    int *arr = new int[n];

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

        cin >> arr[i];

    }



    int m = 1;

    for (int f = 4; m < 100; ++m, f<<=1) {

        if (n / f == 0)

            break;

    }



    int *G = new int[m];

    G[m-1] = 1;

    for (int i = m - 2, f = 4; i >= 0; --i, f<<=1) {

        G[i] = f;

    }



    int count = 0;

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

        int g = G[i];

        for (int j = g; j < n; ++j) {

            int k, key = arr[j];

            for (k = j - g; k >= 0 && arr[k] > key; k-=g, ++count) {

                arr[k + g] = arr[k];

            }

            arr[k+g] = key;

        }

    }



    printf("%d\n", m);

    for (int i = 0; i < m - 1; ++i) {

        printf("%d ", G[i]);

    }

    printf("%d\n", G[m - 1]);

    printf("%d\n", count);

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

        printf("%d\n", arr[i]);

    }



    delete[] arr;

    delete[] G;



    return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstdlib>



using namespace std;



int main(void) {



    int n;

    scanf("%d", &n);



    int *arr = static_cast<int*>(malloc(sizeof(int)*n));

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

        scanf("%d", &arr[i]);

    }



    int m = 1;

    for (int f = 4; m < 100; ++m, f<<=1) {

        if (n / f == 0)

            break;

    }



    int *G = static_cast<int*>(malloc(sizeof(int)*m));

    G[m-1] = 1;

    for (int i = m - 2, f = 4; i >= 0; --i, f<<=1) {

        G[i] = f;

    }



    int count = 0;

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

        int g = G[i];

        for (int j = g; j < n; ++j) {

            int k, key = arr[j];

            for (k = j - g; k >= 0 && arr[k] > key; k-=g, ++count) {

                arr[k + g] = arr[k];

            }

            arr[k+g] = key;

        }

    }



    printf("%d\n", m);

    for (int i = 0; i < m - 1; ++i) {

        printf("%d ", G[i]);

    }

    printf("%d\n", G[m - 1]);

    printf("%d\n", count);

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

        printf("%d\n", arr[i]);

    }



    free(arr);

    free(G);



    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <vector>

#include <utility>

#include <algorithm>

#include <cmath>

using namespace std;



typedef vector<int> vi;



template<typename T>

static inline void p(T x) { cout << x << endl; }



int main()

{

    cin.sync_with_stdio(false);



	int n, cnt = 0;

	cin >> n;



	vi A(n), G;

	for (int &x: A)

		cin >> x;



	for (int i = 1, x = 1; x <= n; x = (pow(3, ++i) - 1) / 2)

		G.push_back(x);

	reverse(G.begin(), G.end());



	for (int g: G)

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

			int v = A[i], j = i - g;

			for(; j >= 0 && A[j] > v; j -= g)

				A[j+g] = A[j], cnt++;

			A[j+g] = v;

		}



	p(G.size());

	for (int &x: G)

		cout << (&x == &G[0] ? "" : " ") << x;

	p("");

	p(cnt);

	for (int x: A)

		p(x);

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <vector>

#include <utility>

#include <algorithm>

#include <cmath>

using namespace std;



static inline void p(int x) { printf("%d\n", x); }



int main()

{

	int n, cnt = 0;

	scanf("%d", &n);



	vector<int> A(n), G;

	for (int &x: A)

		scanf("%d", &x);



	for (int i = 1, x = 1; x <= n; x = (pow(3, ++i) - 1) / 2)

		G.push_back(x);

	reverse(G.begin(), G.end());



	for (int g: G)

		for (auto b = A.begin(), i = b + g, e = A.end(); i != e; i++) {

			int v = *i;

			auto j = i - g;

			for(; j >= b && *j > v; j -= g)

				*(j + g) = *j, cnt++;

			*(j + g) = v;

		}



	p(G.size());

	for (int &x: G)

		printf("%s%d", (&x == &G[0] ? "" : " "), x);

	puts("");

	p(cnt);

	for (int x: A)

		p(x);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <vector>

#include <utility>

#include <algorithm>

#include <cmath>

using namespace std;



typedef vector<int> vi;



template<typename T>

static inline void p(T x) { cout << x << endl; }



int main()

{

	ios::sync_with_stdio(false);

	cin.tie(0);



	int n, cnt = 0;

	cin >> n;



	vi A(n), G;

	for (int &x: A)

		cin >> x;



	for (int i = 1, x = 1; x <= n; x = (pow(3, ++i) - 1) / 2)

		G.push_back(x);

	reverse(G.begin(), G.end());



	for (int g: G)

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

			int v = A[i], j = i - g;

			for(; j >= 0 && A[j] > v; j -= g)

				A[j+g] = A[j], cnt++;

			A[j+g] = v;

		}



	p(G.size());

	for (int &x: G)

		cout << (&x == &G[0] ? "" : " ") << x;

	p("");

	p(cnt);

	for (int x: A)

		p(x);

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <vector>

#include <utility>

#include <algorithm>

#include <cmath>

using namespace std;



static inline void p(int x) { printf("%d\n", x); }



int main()

{

	int n, cnt = 0;

	scanf("%d", &n);



	vector<int> A(n), G;

	for (int &x: A)

		scanf("%d", &x);



	for (int i = 1, x = 1; x <= n; x = (pow(3, ++i) - 1) / 2)

		G.push_back(x);

	reverse(G.begin(), G.end());



	for (int g: G)

		for (auto b = A.begin(), i = b + g, e = A.end(); i != e; i++) {

			int v = *i;

			auto j = i - g;

			for(; j >= b && *j > v; j -= g)

				*(j + g) = *j, cnt++;

			*(j + g) = v;

		}



	p(G.size());

	for (int &x: G)

		printf("%s%d", (&x == &G[0] ? "" : " "), x);

	puts("");

	p(cnt);

	for (int x: A)

		p(x);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

using namespace std;



int cnt;



void insertionSort(int* a, int n, int g){



    int i, j, v;



    for(i = g; i < n; i++){

        v = a[i];

        j = i - g;

        while((j >= 0) && (a[j] > v)){

            a[j + g] = a[j];

            j = j - g;

            cnt++;

        };

        a[j + g] = v;

    }

}



void shellsort(int* a, int n)

{

    cnt = 0;

    int i, p;

    int m;

    int G[15];



    p = 1;

    for(i = 1; i < 20; i++){

        p = p * 3;

        if(p - 1 > 2 * n) break;

    }

    if(i > 1) i = i - 1;

    m = i;



    p = 1;

    for(i = 0; i < m; i++){

        p = p * 3;

        G[m - 1 - i] = (p - 1) / 2;

    }

    cout << m << endl;

    for(i = 0; i < m - 1; i++) cout << G[i] << " ";

    cout << G[m - 1] << endl;



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

        insertionSort(a, n, G[i]);

    }

}



int main()

{

    int i, A[1000000], n;

    cin >> n;

    for(i = 0; i < n; i++) cin >> A[i];



    shellsort(A, n);

    cout << cnt << endl;

    for(i = 0; i < n; i++) cout << A[i] << endl;



    return 0;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>



int cnt;



void insertionSort(int* a, int n, int g){



    int i, j, v;



    for(i = g; i < n; i++){

        v = a[i];

        j = i - g;

        while((j >= 0) && (a[j] > v)){

            a[j + g] = a[j];

            j = j - g;

            cnt++;

        };

        a[j + g] = v;

    }

}



void shellsort(int* a, int n)

{

    cnt = 0;

    int i, p;

    int m;

    int G[15];



    p = 1;

    for(i = 1; i < 20; i++){

        p = p * 3;

        if(p - 1 > 2 * n) break;

    }

    if(i > 1) i = i - 1;

    m = i;



    p = 1;

    for(i = 0; i < m; i++){

        p = p * 3;

        G[m - 1 - i] = (p - 1) / 2;

    }

    printf("%d\n", m);

    for(i = 0; i < m - 1; i++) printf("%d ", G[i]);

    printf("%d\n", G[m - 1]);



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

        insertionSort(a, n, G[i]);

    }

}



int main()

{

    int i, A[1000000], n;

    scanf("%d", &n);

    for(i = 0; i < n; i++) scanf("%d", &A[i]);



    shellsort(A, n);

    printf("%d\n", cnt);

    for(i = 0; i < n; i++) printf("%d\n", A[i]);



    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}   

// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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';

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}




// Optimized solution to the same problem (faster):
#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;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem: