7369: AOE还是单体?
[Creator : ]
Description
牛可乐准备和 n 个怪物厮杀。已知第 i 个怪物的血量为 $a_i$。
牛可乐有两个技能:
第一个技能是蛮牛冲撞,消耗 1 mp,可以对任意单体怪物造成 1 点伤害。
第二个技能是蛮牛践踏,消耗 x mp,可以对全体怪物造成 1 点伤害。
牛可乐想知道,将这些怪物全部击杀,消耗 mp 的最小值的多少?
牛可乐有两个技能:
第一个技能是蛮牛冲撞,消耗 1 mp,可以对任意单体怪物造成 1 点伤害。
第二个技能是蛮牛践踏,消耗 x mp,可以对全体怪物造成 1 点伤害。
牛可乐想知道,将这些怪物全部击杀,消耗 mp 的最小值的多少?
Input
第一行两个正整数 $n,x$,分别代表怪物的数量、每次蛮牛践踏消耗的 mp 值。
第二行 $n$ 个正整数 $a_i$,分别代表每个怪物的血量。
第二行 $n$ 个正整数 $a_i$,分别代表每个怪物的血量。
Output
一个正整数,代表消耗 mp 的最小值。
Constraints
$1≤n≤200000$
$1≤x≤10^9$
$1≤a_i≤10^9$
$1≤x≤10^9$
$1≤a_i≤10^9$
Sample 1 Input
5 2
2 4 5 6 3
Sample 1 Output
11
先对 3 号怪物用 1 次蛮牛冲撞,对 4 号怪物用 2 次蛮牛冲撞,此时消耗 mp 为 3,怪物的血量是 2,4,4,4,3。
然后用 4 次蛮牛践踏,击杀全部怪物,消耗的 mp 总量为 11。
然后用 4 次蛮牛践踏,击杀全部怪物,消耗的 mp 总量为 11。