#P18252. Defeat the Enemies
Defeat the Enemies
Defeat the Enemies
你需要击败 个敌人。第 个敌人最初有 点生命值和 点护甲值。
每次攻击时,你可以选择一个整数伤害值 ,其中 ,对所有敌人造成 点伤害,并支付 的费用。你可以进行任意多次攻击。
伤害优先由护甲承受。击破护甲的那次攻击,其多余伤害不会继续扣除生命值。 具体地,当一个敌人受到 点伤害时:
- 如果它当前的护甲值大于 ,将其护甲值减去 ;
- 否则,将其生命值减去 ;
- 当它的生命值小于或等于 时,该敌人被击败。
求击败所有敌人的最小总费用,以及达到这个最小费用的不同攻击策略数量。
一个策略是攻击伤害依次组成的整数序列 ,其中 。两个策略当且仅当对应序列不同才视为不同;因此攻击顺序也参与区分。
策略数量对 取模。最小总费用不取模。
输入格式
第一行包含整数 ,表示测试用例数。
每个测试用例:
- 第一行包含两个整数 ,分别表示敌人数和生命值、护甲值的上界。
- 第二行包含 个整数 ,表示初始生命值。
- 第三行包含 个整数 ,表示初始护甲值。
- 第四行包含整数 ,表示每次攻击的最大伤害。
- 第五行包含 个整数 ,其中 是一次造成 点伤害的费用。
输出格式
对每个测试用例输出一行,包含两个整数:最小总费用、达到最小费用的策略数量对 取模的结果。
数据范围
- ;
- ;
- ;
- ;
- ;
- 。
同一个输入文件中,所有测试用例的 之和不超过 , 之和不超过 。
样例
4
5 5
3 5 2 1 2
3 1 3 2 3
3
2 3 4
3 2
2 2 2
2 2 2
3
2 3 3
7 6
5 3 4 6 6 3 4
4 6 4 2 3 5 5
4
2 4 6 7
10 100
38 49 79 66 49 89 21 55 13 23
67 56 26 39 56 16 84 50 92 82
11
6 6 7 8 9 9 9 9 9 9 9
9 1
6 4
18 18
99 44387