Language: C++

/*
	Template from @50m_regent
	https://note.mu/50m_regent/n/na84b255e8679
*/

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define INIT cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20);


/* コンテナ基本 */

// コンテナの最初と最後のイテレータ
#define all(x) (x).begin(), (x).end()
// 昇順ソート
#define asc(v) sort(all(v))
// 降順ソート
#define desc(v) sort(all(v), greater<ll>())


/* カウント系 */

// vの中にあるcの個数を数える
#define ct(v, c) count(all(v), c)
// vの中でc未満の要素の個数を数える
#define lh(v, c) lower_bound((v).begin(), (v).end(), c) - (v).begin()
// vの中でcより大きい要素の個数を数える
#define uh(v, c) upper_bound((v).begin(), (v).end(), c) - (v).end()
// vの中でc以下の要素の個数を数える
#define lm(v, c) upper_bound((v).begin(), (v).end(), c) - (v).begin()
// vの中でc以上の要素の個数を数える
#define um(v, c) lower_bound((v).begin(), (v).end(), c) - (v).end()


/* ループ系 */

#define _overload(_1, _2, _3, name, ...) name
// iをaからb-1まで+1しながら繰り返す(b-a回繰り返す)
#define repi(i, a, b) for(ll i = (ll)(a); i < (ll)(b); i++)
// iを0からn-1まで+1しながら繰り返す(n回繰り返す)
#define _rep(i, n) repi(i, 0, n)
// 
#define rep(...) _overload(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
// iをa-1からbまで-1しながら繰り返す(a-b回繰り返す)
#define revi(i, a, b) for(ll i = (ll)(a) - 1; i >= (ll)(b); i--)
// iをnから0まで-1しながら繰り返す(n回繰り返す)
#define _rev(i, n) revi(i, n, 0)
// 
#define rev(...) _overload(__VA_ARGS__, revi, _rev)(__VA_ARGS__)
// vのそれぞれの要素に対して繰り返す
#define each(a, v) for(auto&& a: v)


/* 入力系 */

// 標準入力から何も受け取らない
void in(){}
// 標準入力から複数の値を受け取る
template<typename F, typename... R>
bool in(F& f, R&... r){
	if(cin >> f){
		in(r...);
		return true;
	}else{
		return false;
	}
}
// 標準入力からコンテナvに値を受け取る
#define inv(v) each(i, v) in(i)


/* 出力系 */

// 標準出力
#define out(x) cout << (x)
// 半角スペースを標準出力
#define space() cout << " "
// 改行を標準出力
#define indent() cout << '\n'
// 複数の値を標準出力
void print(){}
template<typename F, typename... R> void print(F f, R... r){out(f), indent(), print(r...);}
// コンテナの値を全て標準出力
#define printv(v) each(i, v) out(i), space(); indent()
// デバッグ用のヘッダをエラー出力
#define debughead(x) cerr << "Line " << __LINE__ << ": " << #x << ": "
// デバッグ用の値をエラー出力
#define debugout(x) cerr << (x) << " "
// デバッグ用の改行をエラー出力
#define debugindent() cerr << '\n'
// デバッグ出力
#define debug(x) debughead(x), debugout(x), debugindent()
// YES or NO を標準出力
#define YN(x) out((x) ? "YES" : "NO"), indent()
// Yes or No を標準出力
#define Yn(x) out((x) ? "Yes" : "No"), indent()
// yes or no を標準出力
#define yn(x) out((x) ? "yes" : "no"), indent()


/* 定数 */

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll LIMIT = 100001;
const ll S_LIMIT = 101;
const ld EPS = 1e-15;
const ld PI = acos(-1);
const ll dx[] = {0, 0, 1, 0, -1, -1, 1, 1, -1};
const ll dy[] = {0, -1, 0, 1, 0, -1, -1, 1, 1};
const string alphabet = "abcdefghijklmnopqrstuvwxyz";
const string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";


/* 基本アルゴリズム */

// 最大公約数
#define gcd __gcd
// 最小公倍数
ll lcm(ll a, ll b){ return a / gcd(a, b) * b; }
// ワーシャルフロイド用配列
ll g[S_LIMIT][S_LIMIT] = {};
// DP用配列
// ll dp[LIMIT][LIMIT] = {};
// MOD対応累乗
ll modpow(ll x, ll n){ return n < 2 ? x : modpow(x * x, n / 2) * (n % 2 ? x : 1) % MOD; }
// MOD対応階乗
ll modfact(ll n){ return n < 2 ? 1 : modfact(n - 1) * n % MOD; }
// MOD対応コンビネーション
ll modcomb(ll n, ll r){ return modfact(n) * modpow(modfact(r), MOD - 2) % MOD * modpow(modfact(n - r), MOD - 2) % MOD; }
// aをmax(a,b)にする
template<typename T> bool chmax(T& a, T b){return (a = max(a, b)) == b;}
// aをmin(a,b)にする
template<typename T> bool chmin(T& a, T b){return (a = min(a, b)) == b;}
// 階乗
ll factorial(ll a){return a < 2 ? 1 : factorial(a - 1) * a;}
// 1～aの総和
ll summation(ll a){return a < 1 ? 0 : (a * a + a) / 2;}
// コンビネーション
ll combination(ll n, ll r){
	ll res = 1;
	rep(i, 1, r + 1){
		res *= n--, res /= i;
	}
	return res;
}
// 素数判定
bool isPrime(ll n){
	rep(i, 2, sqrt(n) + 1){
		if(i > 3){
			i++;
		}
		if(!(n % i)){
			return false;
		}
	}
	return true;
}
// ワーシャルフロイド
void warshall(int n){
	rep(i, n){
		rep(j, n){
			rep(k, n){
				chmin(g[j][k], g[j][i] + g[i][k]);
			}
		}
	}
}
// 約数列挙
vector<int> divisor(int n){
	vector<int> ans;
	rep(i, 1, sqrt(n) + 1){
		if(!(n % i)){
			ans.push_back(i);
			if(i * i < n){
				ans.push_back(n / i);
			}
		}
	}
	return ans;
}
// 素因数分解
map<int, int> factorization(int n){
	map<int, int> ans;
	rep(i, 2, sqrt(n) + 1){
		if(i > 3){
			i++;
		}
		while(!(n%i)){
			ans[i]++, n /= i;
		}
	}
	if(n > 1){
		ans[n]++;
	}
	return ans;
}
// Union-Find
struct UF{
	vector<int> t;
	UF(int size): t(size, -1){}
	int root(int x){ return t[x] < 0 ? x : t[x] = root(t[x]); }
	int size(int x){ return -t[root(x)]; }
	bool isSame(int x, int y){ return root(x) == root(y); }
	bool unite(int x, int y){
		x = root(x), y = root(y);
		if(x != y){
			if(t[y] < t[x]){
				swap(x, y)
			;}
			t[x] += t[y], t[y] = x;
		}
		return x != y;
	}
};

ll n, m, k, tmp, res = 0;
ll s, t = 0;
#define NUM 100

int main(){
	INIT;
	cin >> n >> t;
	vector<pair<int, int>> dish(n);
	int tmp1, tmp2;
	rep(i, n) {
		cin >> tmp1 >> tmp2;
		dish[i].second = tmp1;
		dish[i].first = tmp2;
	}
	desc(dish);
	
	res = dish[0].first;
	// dp[i][j] : 残り時間jで、料理をiまで選んだ時の価値の総和
	int dp[NUM][NUM];
	for(int i=0; i<t; i++) dp[0][i] = 0; // 何も選んでいない状態 dp[0][i] は価値を0で初期化しておく
	rep(i, n) {
		// printf("%d %d\n", dish[i].second, dish[i].first);
	}
	
	rep(i, n) {
		rep(j, t) {
			if(j >= dish[i].second) dp[i+1][j] = max(dp[i][j - dish[i].second] + dish[i].first, dp[i][j]);
			else dp[i+1][j] = dp[i][j];
			// printf("dp[%lld][%lld] = %d\n", i+1, j, dp[i+1][j]);
		}
	}
	
	res += dp[n][t];
	print(res);
	return 0;
}


Compiler output:
In file included from /usr/include/c++/14/bits/stl_algobase.h:71,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:6:
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Iterator2 = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Compare = std::greater<long long int>]':
/usr/include/c++/14/bits/stl_algo.h:1777:14:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<long long int> >]'
 1777 |           if (__comp(__i, __first))
      |               ~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1817:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<long long int> >]'
 1817 |           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1908:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<long long int> >]'
 1908 |           std::__final_insertion_sort(__first, __last, __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4805:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = greater<long long int>]'
 4805 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:233:2:   required from here
   20 | #define desc(v) sort(all(v), greater<ll>())
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/predefined_ops.h:158:30: error: no match for call to '(std::greater<long long int>) (std::pair<int, int>&, std::pair<int, int>&)'
  158 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/string:49,
                 from /usr/include/c++/14/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:52:
/usr/include/c++/14/bits/stl_function.h:394:7: note: candidate: 'constexpr bool std::greater<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = long long int]'
  394 |       operator()(const _Tp& __x, const _Tp& __y) const
      |       ^~~~~~~~
/usr/include/c++/14/bits/stl_function.h:394:29: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'const long long int&'
  394 |       operator()(const _Tp& __x, const _Tp& __y) const
      |                  ~~~~~~~~~~~^~~
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = std::pair<int, int>; _Iterator = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Compare = std::greater<long long int>]':
/usr/include/c++/14/bits/stl_algo.h:1757:20:   required from 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Val_comp_iter<greater<long long int> >]'
 1757 |       while (__comp(__val, __next))
      |              ~~~~~~^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1785:36:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<long long int> >]'
 1785 |             std::__unguarded_linear_insert(__i,
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
 1786 |                                 __gnu_cxx::__ops::__val_comp_iter(__comp));
      |                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1817:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<long long int> >]'
 1817 |           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1908:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<long long int> >]'
 1908 |           std::__final_insertion_sort(__first, __last, __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4805:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = greater<long long int>]'
 4805 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:233:2:   required from here
   20 | #define desc(v) sort(all(v), greater<ll>())
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/predefined_ops.h:240:30: error: no match for call to '(std::greater<long long int>) (std::pair<int, int>&, std::pair<int, int>&)'
  240 |         { return bool(_M_comp(__val, *__it)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_function.h:394:7: note: candidate: 'constexpr bool std::greater<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = long long int]'
  394 |       operator()(const _Tp& __x, const _Tp& __y) const
      |       ^~~~~~~~
/usr/include/c++/14/bits/stl_function.h:394:29: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'const long long int&'
  394 |       operator()(const _Tp& __x, const _Tp& __y) const
      |                  ~~~~~~~~~~~^~~
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Value = std::pair<int, int>; _Compare = std::greater<long long int>]':
/usr/include/c++/14/bits/stl_heap.h:140:48:   required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Distance = long int; _Tp = pair<int, int>; _Compare = __gnu_cxx::__ops::_Iter_comp_val<greater<long long int> >]'
  140 |       while (__holeIndex > __topIndex && __comp(__first + __parent, __value))
      |                                          ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_heap.h:247:23:   required from 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Distance = long int; _Tp = pair<int, int>; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<long long int> >]'
  247 |       std::__push_heap(__first, __holeIndex, __topIndex,
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  248 |                        _GLIBCXX_MOVE(__value), __cmp);
      |                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_heap.h:356:22:   required from 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<long long int> >]'
  356 |           std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
      |           ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  357 |                              __comp);
      |                              ~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1593:23:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<long long int> >]'
 1593 |       std::__make_heap(__first, __middle, __comp);
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1868:25:   required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<long long int> >]'
 1868 |       std::__heap_select(__first, __middle, __last, __comp);
      |       ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1884:27:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx