배낭

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

using namespace std;

int arr[101][100001];
pair<int, int> item[101];
int n, k, w, v;

int func() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
if (item[i].first > j)
arr[i][j] = arr[i - 1][j];
else
arr[i][j] = max(arr[i - 1][j], arr[i - 1][j - item[i].first]
+ item[i].second);
}
}
return arr[n][k];
}

int main() {
scanf("%d %d", &n, &k);

for (int i = 1; i <= n; i++)
{
scanf("%d %d", &w, &v);
item[i].first = w;
item[i].second = v;
}
memset(arr, 0, sizeof(arr));

int result= func();

printf("%d", result);

return 0;
}