## https://yukicoder.me/problems/no/1858 def main(): N, M = map(int, input().split()) vw = [] for _ in range(N): v, w = map(int, input().split()) vw.append((v, w)) vw.sort(key=lambda x : x[0], reverse=True) answer = 0 dp = [-1] * (M + 1) dp[0] = 0 for v, w in vw: # 答えを埋める for m in range(M + 1): if dp[m] != -1: if m + w <= M: ans = dp[m] + v ans *= v answer = max(answer, ans) new_dp = dp.copy() for m in range(M + 1): if dp[m] != -1: if m + w <= M: new_dp[m + w] = max(new_dp[m + w], dp[m] + v) dp = new_dp print(answer) if __name__ == "__main__": main()