#P17950. Soul Link
Soul Link
你是一名法师,需要消灭面前的所有敌人。敌人的等级是 到 的整数,等级为 的敌人有 点生命值,最初共有 个该等级敌人。
你可以使用两种法术:
- Soul Link(灵魂链接):消耗 点魔力,给一个敌人施加灵魂链接效果,持续到该敌人死亡。
- Attack(攻击):消耗 点魔力,对所有带有灵魂链接效果的敌人各造成 点伤害。敌人的生命值变为 时死亡,每死亡一个敌人,你获得 点魔力奖励。
可以使用任意多次法术,但魔力在任何时刻都不能小于 。
求消灭全部敌人所需的最少初始魔力。
输入格式
第一行一个整数 (),表示测试用例数。
每个测试用例第一行两个整数 (,)。
第二行 个整数 ,满足 且 。
输出格式
每个测试用例输出一行一个整数,表示最少初始魔力。
样例 1
输入
2
5 7
5 2 4 1 2
6 4
1 1 4 5 1 4
输出
34
48