有一款名为璀璨宝石(Splendor)的桌游,在重(zhòng)庆交通大学(ZJU)的 102B 宿舍中广受欢迎。小青鱼偶然间认识了 102B 的同学们,并本着“来都来了”的精神,一起玩起了这款桌游。大战了三天三夜之后,他突发奇想:如果稍微修改并简化下游戏规则,我们能找到这个游戏的最优解吗?
本题中的游戏规则与原桌游规则存在出入,请仔细读题。
游戏中有
每张发展卡上都标记了购买这张发展卡所需的
购买发展卡也有助于我们购买后面的发展卡。每张发展卡上还标记了我们以后每次买发展卡时可以抵扣每种里多少个宝石,记为
发展卡也不是随意购买的。游戏初始时会将牌堆的前两张发展卡放到桌上(
初始小青鱼没有任何宝石,也就买不了任何发展卡。游戏会进行很多轮,每一轮中,小青鱼可以进行两种操作之一:
选择两种不同的宝石,拿取这两种宝石各一个。
买走一张桌上的发展卡。
小青鱼想要知道,他最少进行几轮操作可以把
这就到了考验你的宝石之力的时候了!你需要帮助小青鱼找到游戏的最优解,大胜 102B 宿舍的同学们。
输入格式
第一行一个正整数
接下来
输出格式
输出一个数,表示至少进行多少轮才能结束游戏。
样例一
input
5 1 1 1 1 1 0 0 0 0 1 0 0 0 0 5 1 0 0 0 0 2 1 0 0 0 0 0 0 0 1 0 0 2 2 0 0 1 1 0 0 2 1 1 0 0 0 0 0 0 1
output
12
explanation
一种可行的游戏过程如下:
第一轮:拿
第二轮:拿
第三轮:拿
第四轮:拿
第五轮:拿
第六轮:消耗
第七轮:消耗
第八轮:拿
第九轮:消耗
第十轮:消耗
第十一轮:拿
第十二轮:消耗
样例二
见附件下载。
数据范围
对于全部数据:
保证
记
子任务编号 | 特殊性质 | 分值 | ||
---|---|---|---|---|
1 | 无 | |||
2 | 保证 |
|||
3 | 保证 |
|||
4 | 保证 |
|||
5 | 无 | |||
6 | ||||
7 |
时间限制:
空间限制: