| 6 | long long dp[109][100009]; |
| 7 | |
| 8 | int main() { |
| 9 | // ���� |
| 10 | cin >> N >> W; |
| 11 | for (int i = 1; i <= N; i++) cin >> w[i] >> v[i]; |
| 12 | |
| 13 | // �z��̏����� |
| 14 | dp[0][0] = 0; |
| 15 | for (int i = 1; i <= W; i++) dp[0][i] = -(1LL << 60); |
| 16 | |
| 17 | // ���I�v��@ |
| 18 | for (int i = 1; i <= N; i++) { |
| 19 | for (int j = 0; j <= W; j++) { |
| 20 | // j<w[i] �̂Ƃ��A���@ B ���Ƃ�I�ѕ����ł��Ȃ� |
| 21 | if (j < w[i]) dp[i][j] = dp[i - 1][j]; |
| 22 | // j>=w[i] �̂Ƃ��A���@ A�E���@ B �ǂ�����I�ׂ� |
| 23 | if (j >= w[i]) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); |
| 24 | } |
| 25 | } |
| 26 | |
| 27 | // �������o�� |
| 28 | long long Answer = 0; |
| 29 | for (int i = 0; i <= W; i++) Answer = max(Answer, dp[N][i]); |
| 30 | cout << Answer << endl; |
| 31 | return 0; |
| 32 | } |