// // Yukicoder // No.1858 // //#include "stdafx.h" #include #include #include #include //list #include //tree #include //連想配列 #include //hash #include //hash #include #include #include #include using namespace std; typedef unsigned long long ULL; typedef signed long long SLL; typedef unsigned int UINT; #define START (0) #define RIGHT (1) #define UP (2) #define LEFT (3) #define DOWN (4) #define DATA_MAX (1000000) #define FMAX(a,b) ((a)>(b)?(a):(b)) #define FMIN(a,b) ((a)<(b)?(a):(b)) //vectorは便利だが処理時間がかかるので注意 vector > memo2;//二次元可変配列 vector memo1; SLL H ,A, B, T, F, N, M, Result; SLL backet[1000005]; SLL dp[5005][5005]; struct BOX { SLL w; SLL v; }; BOX box[5005]; //美しさの降順にソート int compare(const BOX * a, const BOX *b) { if (a->v < b->v) return (1); else if (a->v > b->v) return (-1); return (0); } int main(int argc, char *argv[]) { SLL ans = 0; // 入力部 cin >> N; cin >> M; for (int i = 0; i < N; i++) { cin >> box[i].v; cin >> box[i].w; } //Sorting qsort(&box[0], N, sizeof(BOX), (int(*)(const void*,const void*))compare); //ソート結果のデバッグ出力 /* for (int i = 0; i < N; i++) { cout << "V=" << box[i].v << ",W=" << box[i].w << endl; }*/ //最初の1行目(i=0) for (int j = 0; j <= M; j++) { if(j >= box[0].w) dp[0][j] = box[0].v; } //美しさの降順になっているため、i番目以下で最も美しさの小さいものはi番目である for(int i=1;i= box[i].w) { // "j" の容量のときに、下記AとBを比較する //    A: 今回の宝石を入れた場合の価値 → dp[i - 1][j - box[i].w] + box[i].v //   B: 今回の宝石を入れなかった場合の価値 → dp[i - 1][j] if (dp[i - 1][j - box[i].w] + box[i].v > dp[i - 1][j]) { dp[i][j] = dp[i - 1][j - box[i].w] + box[i].v; ans = FMAX(ans, box[i].v * dp[i][j]); } else { dp[i][j] = dp[i - 1][j]; } } else { dp[i][j] = dp[i - 1][j]; } } cout << ans << endl; /* for (int i = 0; i < N; i++) { for (int j = 0; j <= M; j++)//ナップサックの容量を1つづつ増やしていく { cout << dp[i][j] << ","; } cout << endl; } */ /////////////////// //cout << endl; //getchar(); return 0; //end }