记录编号	380385	评测结果	AAAAAAAAAA
题目名称	采药(加强版)	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.850 s
提交时间	2017-03-09 08:31:38	内存使用	6.04 MiB

//\
2230.采药(加强版)

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define is_num(tmp) (tmp<='9' and tmp>='0')
inline int in(void){
	char tmp(getchar());
	int res(0),f(1);
	while(!(is_num(tmp)||tmp=='-'))tmp=getchar();
	if(tmp=='-')f=-1,tmp=getchar();
	while(is_num(tmp))
		res=(res<<1)+(res<<3)+(tmp^48),
		tmp=getchar();
	return res*f;
}//\
#define LOCAL
#define MAXN 250250
template<typename T>
T my_min(const T&a,const T&b){
	return a<b?a:b;
}
template<typename T>
T my_max(const T&a,const T&b){
	return a<b?b:a;
}
int _c[MAXN],_v[MAXN],_w[MAXN],_cnt,cnt;
int v[MAXN],w[MAXN];
int dp[MAXN];
int N,W,s1,s2;
int main(){
#ifndef LOCAL
	freopen("crazytime.in","r",stdin);
	freopen("crazytime.out","w",stdout);
#endif
	N=in(),W=in();
	for(int i=1;i<=N;++i){
		s1=in(),s2=in();
		bool flag=true;
		for(int i=1;i<=_cnt;++i){
			if(_v[i]==s1&&_w[i]==s2){
				++_c[i],flag=false;
				break;
			}
		}
		if(flag){
			++_cnt;
			_v[_cnt]=s1,_w[_cnt]=s2;
			_c[_cnt]=1;
		}
	}
	for(int i=1;i<=_cnt;++i){
		int t=1;
		while(_c[i]>=t){
			++cnt;
			v[cnt]=_v[i]*t;
			w[cnt]=_w[i]*t;
			_c[i]-=t;
			t*=2;
		}
		++cnt;
		v[cnt]=_c[i]*_v[i];
		w[cnt]=_c[i]*_w[i];
	}
	for(int i=1;i<=cnt;++i){
		for(int j=W;j>=v[i];--j){
			dp[j]=my_max(dp[j],dp[j-v[i]]+w[i]);
		}
	}
	printf("%d",dp[W]);
	return 0;
}