평범한 배낭
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define pii pair<int, int>
int N, K;
vector<pii> inputs;
bool cmp(pii& p1, pii& p2) { return p1.first < p2.first; }
int main() {
cin >> N >> K; // 물품의 수, 최대 무게
for (int i = 0; i < N; i++) {
int w, v; // 무게, 가치
cin >> w >> v;
inputs.push_back(make_pair(w, v));
}
// 가벼운 물품부터 처리하기 위해 오름차순 정렬
sort(inputs.begin(), inputs.end(), cmp);
// 무게 만큼의 배열을 만듦 (무게를 인덱스로)
vector<int> values(K + 1, 0);
for (int i = 1; i <= inputs.size(); i++) {
int pivot_weight, pivot_value;
tie(pivot_weight, pivot_value) = inputs[i - 1];
// 이미 오름차순 정렬 시켜서 이런 값 계산 안해도 됨
// + 인덱스에 이거 집어넣으면 안됨
if (pivot_weight > K) break;
vector<int> tmpValues(values.begin(), values.end());
// DP 진행
tmpValues[pivot_weight] = max(values[pivot_weight], pivot_value);
for (int j = pivot_weight + 1; j <= K; j++) {
tmpValues[j] = max(values[j], values[j - pivot_weight] + pivot_value);
}
copy(tmpValues.begin(), tmpValues.end(), values.begin());
}
cout << values.back() << endl;
return 0;
}