#P18099. The Best Card
The Best Card
The Best Card
题目描述
游戏持续 个回合。敌人的初始毒性层数为 。
有 张卡牌。第 张卡在第 回合开始时使用,使毒性增加 层。同一回合可以使用多张卡,毒性增加量相加。
每回合结束时,设当前毒性为 :若 ,敌人受到 点伤害,然后毒性减 ;若 ,则什么也不发生。
游戏开始前,你可以强化 次。每次任选一张卡,将其 增加 ;同一张卡可以被重复强化。求进行这些强化后,敌人在整个游戏中受到的最大总伤害。
输入格式
第一行一个整数 。
每组数据包含三行:第一行两个整数 ;第二行 个整数 ;第三行 个整数 。
输出格式
每组数据输出一行,一个整数,表示最大总伤害。
数据范围
,,;,每组数据满足 。一个输入文件中所有 之和不超过 。 不保证有序,也不保证互不相同。
样例 1
输入
5
2 1
2 3
1 4
2 2
3 4
1 3
4 1
3 3 1 4
4 4 1 5
3 0
16 27 62
9 88 11
3 5
9 3 1
8 3 3
输出
13
37
63
3335
126