問題を定式化すれば、いわゆる 01 knapsack と呼ばれる問題です。

容量 \(T - S\) の knapsack に、重さ \(C_i\)、 価値 \(P_i\) の商品 \(i \ (1 \le i \le N)\) を詰めるときの価値の最大化です。これは

\(\mathrm{dp}[i][j] =\) 商品 \(i\) までを入れるかどうか決めて、重さ \(j\) を使っている時の価値の総和の最大値

とした dp を考えることで、状態 \(O(N(T - S))\) 遷移 \(O(1)\) で解く事ができます。実際には、 \(i\) の添字は持たずに、遷移の順番 \(j\) の降順にするテクニックがよく用いられます。

実装例

n, t, s = map(int, input().split())

dp = [0] * (t - s + 1)
for i in range(n):
    c, p = map(int, input().split())
    for j in reversed(range(t - s + 1 - c)):
        dp[j + c] = max(dp[j + c], dp[j] + p)

print(max(dp))