この問題は、 動的計画法 (DP) で解くことができます。
インターネット上には多種多様な DP の教材が揃っているため、 DP の概念の導入はそちらに譲ります。

DP テーブル \(dp[\) 必要な時間の合計 \(]=\{\) 評価点の合計の最大値 \(\}\) を考えます。

• \(dp[0]=0\) 、そのほかの \(i\) について \(dp[i]=-\infty\) で初期化します。
• \(i=1,2,\dots,N\) について、以下を繰り返す。
  • \(dp[j] \ge 0\) であれば、 \(dp[j+T_i]\) に \(dp[j]+R_i\) を遷移させる。
  • この \(j\) を降順に回すことで、 in-place に求解できる。
    • in-place とは、追加の記憶領域をほとんど利用せずに計算する方法です。 DP のための配列を複数用意する方法もありますが、 \(j\) を降順に回すと DP に使う配列が \(1\) つだけで済みます。

最終的に、 \(dp[i]\) の \(0 \le i \le M\) にわたる最大値が答えとなります。
時間計算量は \(O(NM)\) 、空間計算量は \(O(M)\) です。

上記の DP 中に、なぜ \(j\) を昇順に回してはいけないのでしょうか?
例えば \(T_1=2, R_1=5\) の宿題が最初に来たとします。

• \(dp[2]\) に \(dp[0]+5=0+5\) が遷移する。
• \(dp[4]\) に \(dp[2]+5=5+5=10\) が遷移する。
• ところが、この時点での \(dp[2]\) は既に \(dp[0]\) からこの宿題をやった場合に対応するので、同じ宿題を複数やってしまったことになって、本問題設定では不適切である。

ちなみに、 \(j\) を昇順に回した場合の DP は全ての宿題を何度でも無制限に完了できる場合に対応します。
なお、 in-place でない実装をすることでもこの問題を回避することもできます。

意欲ある読者のために、現在 AtCoder 上で利用可能な DP の教材を挙げます。

• DP まとめコンテスト
  • 最も手の付けやすいと思われる DP の問題集です。基礎的な DP はこちらで網羅することができます。
• Typical DP Contest
  • 古い教材なので癖があるものの、現在でも通用する難しい DP も扱われています。
• Next DP Contest
  • 2026 年 5 月 5 日に開催された、最新の DP の教材です。非常に高度な内容です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ll N,M;
  cin >> N >> M;
  vector<ll> dp(M+1,-4e18);
  dp[0]=0;
  for(ll i=0;i<N;i++){
    ll R,T;
    cin >> R >> T;
    for(ll j=M-T;j>=0;j--){
      if(dp[j]>=0){
        dp[j+T]=max(dp[j+T],dp[j]+R);
      }
    }
  }
  cout << (*max_element(dp.begin(),dp.end())) << "\n";
  return 0;
}