На все товары в магазинах действуют скидки по случаю Дня дураков 15 мая. Таким образом, вы можете купить товар на сумму X манатов за ⌊2YX⌋ манатов, предъявив Y купонов на скидку. У вас есть M купонов на скидку, и вы хотите купить N товаров. Вы также знаете цену каждого товара A1, A2, ... , AN . Какова минимальная сумма денег, необходимая для покупки всех товаров?
Примечание: Здесь ⌊X⌋, означает целую часть числа Х .
В первой строке даётся два целых числа – N и M (1≤N,M≤105) , во второй строке даётся N целых – A1,A2,...,AN (1≤Ai≤109) .
Выведите минимальную сумму денег, необходимую для покупки всех товаров.
В первом примере все товары на 10 манатов можно приобрести следующим образом: Первый товар 3 маната без предъявления купона на скидку. Второй предмет можно получить, использовав 2 купона на скидку ⌊2215⌋ = 3 маната, а третий предмет, предъявив 1 купон на скидку за 4 маната. В итоге получилось: 3+3+4=10.
Во втором примере используя 1000 купонов на скидку, вы можете купить товар на 1000000 манатов за 0 манатов.
Данная задача как указано внизу состоит из 5 подзадач: