阿里 22号 笔试第二题

int n, m, A, B, C;
vector<vector<pair<int, int>>> flag;
vector<int> res1, res2, res3;
void do_dp(int pos, vector<int>& res) {
	int tol = flag[pos].size();
	vector<vector<int>> st(tol+1, vector<int>(m + 1, 0));
	for (int i = 1; i <= tol; i++) {
		for (int j = 0; j <= m; j++) {
			st[i][j] = st[i - 1][j];
			int cost = flag[pos][i - 1].second;
			if (j >= cost) {
				st[i][j] = max(st[i][j], st[i][j - cost] + flag[pos][i - 1].first);
			}
		}
	}
	for (int i = 0; i <=m; i++) {
		res.push_back(st[tol][i]);
	}
}

int main() {
	C = 0;
	cin >> n >> m >> A >> B;
	flag.resize(3);
	for (int i = 0; i < n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 1) flag[0].push_back({ b,c });
		else if (a == 2) flag[1].push_back({ b,c });
		else flag[2].push_back({ b,c });
	}

	do_dp(0, res1);
	do_dp(1, res2);
	do_dp(2, res3);
	int res = 0;
	for (int i = 0; i <= m; i++) {
		for (int j = 0; j + i <= m; j++) {
			int k = m - i - j;
			res = max(res, (A + res1[i]) * (B + res2[j]) + res3[k]);
		}
	}
	cout << res << endl;
	return 0;
}