#P18269. Let's Go! New Adventure
Let's Go! New Adventure
Let's Go! New Adventure
题目描述
在 Pigeland,Pishin 是一款流行的开放世界动作角色扮演游戏。玩家可以使用多个角色,每个角色都有独立的冒险等级。角色初始等级为 ,最高等级为 。
从等级 升到等级 需要获得 点经验。升级越来越困难,因此 。升级所需经验可以为零。
Grammy 计划接下来玩 天。她有无限多个角色,但这些角色在这 天开始时的等级都是 。每天她必须恰好选择一个角色游玩。一个角色一旦停止使用,以后的任何一天都不能再使用,因此同一个角色只能在连续若干天内使用。
第 天,所使用的角色会获得 点经验。如果某个角色在第 天到第 天连续使用,其最终等级为满足
的最大整数 ,其中 。即使这一段获得的经验为零,也按这个公式计入免费升级的等级。
她希望所有角色最终冒险等级的总和尽可能大,同时又不想使用太多不同角色。给定罚分系数 ,设她使用的不同角色数为 ,求
的最大值。所有 天都要安排角色,因此 ,答案可能为负。
输入格式
第一行一个整数 ,表示测试用例数。
每个测试用例包含三行:
- 第一行三个整数 。
- 第二行 个整数 。
- 第三行 个整数 ,按非递减顺序给出。
输出格式
每个测试用例输出一行一个整数,表示最大目标值。答案不取模,应使用 64 位有符号整数保存。
数据范围
- 。
- ,。
- ,每个测试用例的 。
- ,,每个测试用例的 。
- 每个输入文件中,所有测试用例的 之和、 之和分别不超过 。
样例
2
5 4 2
1 0 3 1 2
0 1 1 2
4 5 1
7 16 23 4
1 3 6 20 20
3
6
样例说明
第一个测试用例中,可以前三天使用同一个角色,升到等级 ;后两天使用另一个角色,升到等级 。目标值为 。
第二个测试用例中,每天使用一个新角色,最终等级分别为 ,目标值为 。