装饰珠
解题思路：
根据题意，6件装备这个信息没有用，因为最终是按照所有装备中装饰物的总数来算的。
看数据范围，等级只有1、2、3、4，并且1级的可以任意放，2级的只能放2、3、4级，3级的只能放3、4级，4级的只能放4级。
所以这是一个分组背包问题。按照等级对装饰物分组。
背包问题的体积在这里就是可以放置的槽位的总数。
用f[i][j]表示放了i种装饰物，总共放了j个装饰物的最大总价值。
这里与背包问题不一样，第二维不表示“体积不超过j”，而表示“体积为j”，因为递推需要保证填满j，不然无法递推。
若放t个第i种装饰物的价值为w[t]，则 f[i][j] 可以由 max(f[i - 1][j - t] + w[t]) 推得。
因为这是一个分组背包问题，所以降维方法也一样。
考虑到等级的限制，需要从较高等级的装饰物开始枚举。
import sys; readline = sys.stdin.readline
read = lambda: [int(x) for x in readline().split()]
alloc = lambda *s: len(s) != 1 and [alloc(*s[1:]) for i in range(int(s[0]) + 2)] or [0] * int(s[0] + 2)
bet = lambda a, b : a <= b and range(a, b + 1) or range(a, b - 1, -1)
count = [0] * 5
for i in range(6):
for t in read()[1:]:
count[t] += 1
m = sum(count)
n, = read()
w = [[] for _ in range(5)]
for i in bet(1, n):
a, b, *c = read()
w[a].append(c)
f = alloc(m)
# f[i][j] 表示按照从高等级开始放入珠子，放了i个，并且总共放了j个装饰物的最大价值。
# 这里按照背包问题的降维方法，去掉了i对应的那一维
able = 0
for level in bet(4, 1):
able += count[level] # j可以达到的最大值
for vec in w[level]:
for j in bet(able, 0): # 为了降维，j从大开始枚举
for i, v in enumerate(vec):
if j - i - 1 < 0: break
# 这里不能用f[j]=max(f[j],f[j-i-1]+v)，否则可能会超时
if f[j] < f[j - i - 1] + v:
f[j] = f[j - i - 1] + v
print(max(f[:]))