913C.md (1927B)
1 Source: https://codeforces.com/problemset/problem/913/C 2 3 C. Party Lemonade 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 A New Year party is not a New Year party without lemonade! As usual, you are expecting a lot of guests, and buying lemonade has already become a pleasant necessity. 22 23 Your favorite store sells lemonade in bottles of *n* different volumes at different costs. A single bottle of type *i* has volume 2*i* - 1 liters and costs *c**i* roubles. The number of bottles of each type in the store can be considered infinite. 24 25 You want to buy at least *L* liters of lemonade. How many roubles do you have to spend? 26 27 Input 28 29 The first line contains two integers *n* and *L* (1 ≤ *n* ≤ 30; 1 ≤ *L* ≤ 109) — the number of types of bottles in the store and the required amount of lemonade in liters, respectively. 30 31 The second line contains *n* integers *c*1, *c*2, ..., *c**n* (1 ≤ *c**i* ≤ 109) — the costs of bottles of different types. 32 33 Output 34 35 Output a single integer — the smallest number of roubles you have to pay in order to buy at least *L* liters of lemonade. 36 37 Examples 38 39 Input 40 41 ``` 42 4 12 43 20 30 70 90 44 ``` 45 46 Output 47 48 ``` 49 150 50 ``` 51 52 Input 53 54 ``` 55 4 3 56 10000 1000 100 10 57 ``` 58 59 Output 60 61 ``` 62 10 63 ``` 64 65 Input 66 67 ``` 68 4 3 69 10 100 1000 10000 70 ``` 71 72 Output 73 74 ``` 75 30 76 ``` 77 78 Input 79 80 ``` 81 5 787787787 82 123456789 234567890 345678901 456789012 987654321 83 ``` 84 85 Output 86 87 ``` 88 44981600785557577 89 ``` 90 91 Note 92 93 In the first example you should buy one 8-liter bottle for 90 roubles and two 2-liter bottles for 30 roubles each. In total you'll get 12 liters of lemonade for just 150 roubles. 94 95 In the second example, even though you need only 3 liters, it's cheaper to buy a single 8-liter bottle for 10 roubles. 96 97 In the third example it's best to buy three 1-liter bottles for 10 roubles each, getting three liters for 30 roubles.