Какая же новогодняя вечеринка обходится без лимонада! Вы, как обычно, ожидаете много гостей, и покупка лимонада уже стала приятной необходимостью.
Ваш любимый магазин продает лимонад в бутылках n различных объемов по разным ценам. Бутылка типа i имеет объем 2i - 1 литров и стоит ci рублей. Количество бутылок каждого типа в магазине можно считать бесконечным.
Вы хотите купить не менее L литров лимонада. Во сколько рублей вам это обойдется?
Выходные данные
Выведите единственное число — минимальное количество рублей, которое придется потратить, чтобы купить не менее L литров лимонада.
Примечание
В первом примере вам следует купить бутылку объемом 8 литров за 90 рублей и две бутылки объемом 2 литра за 30 рублей каждую. В сумме вы получите 12 литров лимонада всего за 150 рублей.
Во втором примере, хоть вам и нужно всего 3 литра, дешевле всего купить одну восьмилитровую бутылку по акции за 10 рублей.
В третьем примере выгоднее всего купить три литровые бутылки по 10 рублей каждая, получив требуемые три литра за 30 рублей.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 12
20 30 70 90
|
150
|
|
2
|
4 3
10000 1000 100 10
|
10
|
|
3
|
4 3
10 100 1000 10000
|
30
|
|
4
|
5 787787787
123456789 234567890 345678901 456789012 987654321
|
44981600785557577
|