记录编号	144633	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008]魔兽地图	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	1.808 s
提交时间	2014-12-24 20:25:11	内存使用	82.94 MiB

/*====================Asm.Def========================*/
#include <iostream>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <queue>
using namespace std;
inline void getd(int &x){
	char c = getchar();
	bool minus = 0;
	while(!isdigit(c) && c != '-')c = getchar();
	if(c == '-')minus = 1, c = getchar();
	x = c - '0';
	while(isdigit(c = getchar()))x = x * 10 + c - '0';
	if(minus)x = -x;
}
/*======================================================*/
const int maxn = 53, maxm = 2003, maxc = 102, INF = 0x7fffffff;
typedef long long LL;
struct Node{
	Node *son, *bro;
	int maxcost, maxcnt, cnt, pri, val;
	int f[maxc][maxm], S[maxc][maxm];
	void dfs();
	void dp();
}node[maxn], *Root;
int N, M, tmp[maxm];

void Node::dfs(){
	if(son == NULL){
		maxcnt = min(M / pri, maxcnt);
		if((LL)maxcnt * pri > M)maxcnt = 0, maxcost = 0;
		else maxcost = maxcnt * pri;
		return;
	}
	Node *it = son;
	maxcnt = INF;
	while(it != NULL){
		it->dfs();
		maxcost = min(M, maxcost + it->maxcost);
		if((LL)it->pri * it->cnt > M)
			pri = 0, maxcnt = 0;
		else{
			pri += it->pri * it->cnt;
			maxcnt = min(maxcnt, it->maxcnt / it->cnt);
		}
		it = it->bro;
	}
	if(pri)maxcnt = min(M / pri, maxcnt);
	else maxcnt = 0;
}

inline void init(){
	getd(N), getd(M);
	unsigned long long NotRoot = 1;
	int i, j, k, ch;
	for(i = 1;i <= N;++i){
		getd(node[i].val);
		while(!isalpha(ch = getchar()));
		if(ch == 'A'){
			getd(j);getd(k);
			getd(node[k].cnt);
			node[i].son = node + k;
			NotRoot |= (1ll << k);
			while(--j){
				getd(k);getd(node[k].cnt);
				node[k].bro = node[i].son;
				node[i].son = node + k;
				NotRoot |= (1ll << k);
			}
		}
		else
			getd(node[i].pri), getd(node[i].maxcnt);
	}
	NotRoot = (~NotRoot) & (NotRoot + 1);
	i = 0;
	while(NotRoot > 1)++i, NotRoot >>= 1;
	Root = node + i;
	Root->dfs();
}

inline void AddTo(int *S, int *f, int limS, int limf){
	int i, j;
	for(i = 1;i <= limS;++i){
		tmp[i] = 0;
		for(j = 0;j <= min(limf, i);++j)if(f[j] + S[i-j] > tmp[i])
			tmp[i] = f[j] + S[i-j];
	}
	for(i = 1;i <= limS;++i)S[i] = tmp[i];
}

void Node::dp(){
	int i, j;
	Node *it;
	if(son != NULL)for(it = son;it != NULL;it = it->bro){
		it->dp();
		for(i = 0;i <= maxcnt;++i)
			AddTo(S[i], it->f[i*it->cnt], maxcost, it->maxcost);
		for(j = 1;j <= maxcost;++j)
			f[maxcnt][j] = max(S[maxcnt][j], f[maxcnt][j-1]);
	}
	for(i = maxcnt-1;i >= 0;--i)for(j = 1;j <= maxcost;++j){
		f[i][j] = max(f[i][j-1], S[i][j]);
		if(j >= pri && f[i+1][j-pri] + val > f[i][j])
			f[i][j] = f[i+1][j-pri] + val;
	}
}

int main(){
	#if defined DEBUG
	freopen("test", "r", stdin);
	#else
	freopen("bzoj_1017.in", "r", stdin);
	freopen("bzoj_1017.out", "w", stdout);
	#endif
	init();
	
	Root->dp();
	printf("%d\n", Root->f[0][Root->maxcost]);
	
	#if defined DEBUG
	cout << endl << (double)clock()/CLOCKS_PER_SEC << endl;
	#endif
	return 0;
}