[골5] 12865 - 평범한 배낭

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#pragma region 입출력 속도향상

#define FAST_IO() \
{\
	ios::sync_with_stdio(false);\
	cin.tie(NULL); \
	cout.tie(NULL); \
}\

#pragma endregion

vector<int> w, v;
vector<vector<int>> dp;

int main()
{
	FAST_IO();

	int n, k;
	cin >> n >> k;
	w.resize(n + 1);
	v.resize(n + 1);
	dp.resize(n + 1, vector<int>(k + 1));

	for (int i = 1; i <= n; i++)
		cin >> w[i] >> v[i];

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= k; j++)
		{
			if (j - w[i] >= 0)
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);

			else
				dp[i][j] = dp[i - 1][j];
		}
	}
	cout << dp[n][k];
	return 0;
}