|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
G - Go Kill the Monsters
Languages: C, C++, Java, Python, Kotlin, C#
Time & Memory limits: (details)
You're playing a new game. There are $n$ monsters in this game, each with a specific strength. The strength of the $i$-th monster is $a_i$, which means that it costs $a_i$ energy coins to kill that monster ``by hand''. In the game, there is also a nuke button, that can be pressed at multiple moments during the game, as many times as you want. Pressing the nuke button costs $K$ energy coins; consequently, half of the monsters are killed instantly at random with no additional costs. Namely, if there are currently $m$ monsters alive, after pressing the nuke button, $\lfloor\frac{m}{2}\rfloor$ random monsters will be killed.
Given the strength of all the monsters and the cost of pressing the nuke button, find the minimum total cost (in energy coins) needed to kill all the monsters, in the worst case.
Input
The first line contains two numbers separated by white space, $n, K$ ($1 \leq n \leq 10^5, 1 \leq K \leq 10^9$), that is the number of monsters and the cost of pressing the killing button, respectively. The second line contains $n$ numbers, $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^9$), they are the strength of each of the monsters.
Output
Print a single integer being the minimum total cost needed to kill all the monsters in the worst case.
Sample test(s)
Input
5 3
3 3 3 4 5
Output
14