After several latest reforms many tourists are planning to visit Berland, and Berland people understood that it's an opportunity to earn money and changed their jobs to attract tourists. Petya, for example, left the IT corporation he had been working for and started to sell souvenirs at the market.
This morning, as usual, Petya will come to the market. Petya has n different souvenirs to sell; ith souvenir is characterised by its weight wi and cost ci. Petya knows that he might not be able to carry all the souvenirs to the market. So Petya wants to choose a subset of souvenirs such that its total weight is not greater than m, and total cost is maximum possible.
Help Petya to determine maximum possible total cost.
The first line contains two integers n and m (1 ≤ n ≤ 100000, 1 ≤ m ≤ 300000) — the number of Petya's souvenirs and total weight that he can carry to the market.
Then n lines follow. ith line contains two integers wi and ci (1 ≤ wi ≤ 3, 1 ≤ ci ≤ 109) — the weight and the cost ofith souvenir.
Print one number — maximum possible total cost of souvenirs that Petya can carry to the market.
1 1
2 1
0
2 2
1 3
2 2
3
4 3
3 10
2 7
2 8
1 1
10
题目大意就是0-1背包问题，然后看着逆天的数据范围，O(nm)的算法怕是去卡评测机的。
只能另想出路了。注意到每个物品的最大重量为3，突破口应该就在这儿。
先按照物品的重量分类，排序(从大到小，因为同种重量选价值大不会更劣)，求前缀和。
考虑枚举重量为3的物品选择的物品的数量。考虑对剩下物品dp。不难证明容量+1后对策略的影响只有：
- 加入一个重量为1的物品。
- 拿走一个重量为1的物品加入一个重量为2的物品。
（大概就是因为每次改变的物品重量和不会超过2，如果改变的物品重量和超过2，那么两边一定存在1个重量和为2的物品集合，把现在这个集合里的替换为新的集合中会更优，这样会矛盾）
不过暴力记下每种重量的物品选择的数量也可以dp。讨论一下发现和这个操作是类似的。
Code
1 /** 2 * Codeforces 3 * Problem#808E 4 * Accepted 5 * Time:31ms 6 * Memory:9400k 7 */ 8 #include<iostream> 9 #include<cstdio> 10 #include<ctime> 11 #include<cctype> 12 #include<cstring> 13 #include<cstdlib> 14 #include<fstream> 15 #include<sstream> 16 #include<algorithm> 17 #include<map> 18 #include<set> 19 #include<stack> 20 #include<queue> 21 #include<vector> 22 #include<stack> 23 #ifndef WIN32 24 #define Auto "%lld" 25 #else 26 #define Auto "%I64d" 27 #endif 28 using namespace std; 29 typedef bool boolean; 30 #define inf 0xfffffff 31 #define smin(a, b) a = min(a, b) 32 #define smax(a, b) a = max(a, b) 33 #define max3(a, b, c) max(a, max(b, c)) 34 #define min3(a, b, c) min(a, min(b, c)) 35 template<typename T> 36 inline boolean readInteger(T& u){ 37 char x; 38 int aFlag = 1; 39 while(!isdigit((x = getchar())) && x != '-' && x != -1); 40 if(x == -1) { 41 ungetc(x, stdin); 42 return false; 43 } 44 if(x == '-'){ 45 x = getchar(); 46 aFlag = -1; 47 } 48 for(u = x - '0'; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - '0'); 49 ungetc(x, stdin); 50 u *= aFlag; 51 return true; 52 } 53 54 #define LL long long 55 56 typedef class Data { 57 public: 58 LL val; 59 int s1, s2; 60 61 Data():val(0), s1(0), s2(0) { } 62 }Data; 63 64 int n, m; 65 Data* f; 66 int cnt[4] = {0, 0, 0, 0}; 67 int vs[4][100005]; 68 LL s[4][100005]; 69 70 inline void init() { 71 readInteger(n); 72 readInteger(m); 73 f = new Data[(const int)(m + 1)]; 74 for(int i = 1, v, w; i <= n; i++) { 75 readInteger(w); 76 readInteger(v); 77 vs[w][++cnt[w]] = v; 78 } 79 } 80 81 boolean cmpare (const int& a, const int& b) { 82 return a > b; 83 } 84 85 LL res = 0; 86 87 inline void solve() { 88 for(int i = 1; i <= 3; i++) { 89 sort(vs[i] + 1, vs[i] + cnt[i] + 1, cmpare); 90 s[i][0] = 0; 91 for(int j = 1; j <= cnt[i]; j++) 92 s[i][j] = s[i][j - 1] + vs[i][j]; 93 } 94 95 for(int i = 1; i <= m; i++) { 96 if(f[i - 1].s1 < cnt[1] && f[i].val < f[i - 1].val + vs[1][f[i - 1].s1 + 1]) { 97 f[i].val = f[i - 1].val + vs[1][f[i - 1].s1 + 1]; 98 f[i].s1 = f[i - 1].s1 + 1, f[i].s2 = f[i - 1].s2; 99 } 100 if(i >= 2 && f[i - 2].s2 < cnt[2] && f[i].val < f[i - 2].val + vs[2][f[i - 2].s2 + 1]) { 101 f[i].val = f[i - 2].val + vs[2][f[i - 2].s2 + 1]; 102 f[i].s2 = f[i - 2].s2 + 1, f[i].s1 = f[i - 2].s1; 103 } 104 } 105 106 for(int i = 0; i <= m; i++) 107 if((m - f[i].s1 - f[i].s2 * 2) / 3 <= cnt[3]) 108 smax(res, f[i].val + s[3][(m - f[i].s1 - f[i].s2 * 2) / 3]); 109 else 110 smax(res, f[i].val + s[3][cnt[3]]); 111 printf(Auto, res); 112 } 113 114 int main() { 115 init(); 116 solve(); 117 return 0; 118 }