#include <bits/stdc++.h> using namespace std; /* clang-format on */ const auto io_sync_off = []() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return nullptr; } (); int w[1000]; int v[1000]; int dp[1000]; int main() { int n, V; cin >> n >> V; for (int i = 0; i < n; i++) { cin >> v[i] >> w[i]; } memset(dp, 0, sizeof dp); for (int i = 0; i < n; i++) { for (int j = v[i]; j <= V; j++) { //可以重复选(重复叠加同一个物品),所以用顺序,若只有1件物品,倒序推就不会重复计算 dp[j] = max(dp[j], dp[j - v[i]] + w[i]); } } int mx = dp[V]; memset(dp, -0x3f, sizeof dp); dp[0] = 0; for (int i = 0; i < n; i++) { for (int j = v[i]; j <= V; j++) { dp[j] = max(dp[j], dp[j - v[i]] + w[i]); } } printf("%d\n%d\n", max(mx, 0), max(dp[V], 0)); }