贪心 + DFS

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.

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.

You want to buy at least L liters of lemonade. How many roubles do you have to spend?

Input

The first line contains two integers n and L (1 ≤ n ≤ 30; 1 ≤ L ≤ 10⁹) — the number of types of bottles in the store and the required amount of lemonade in liters, respectively.

The second line contains n integers c₁, c₂, ..., c_n (1 ≤ c_i ≤ 10⁹) — the costs of bottles of different types.

Output

Output a single integer — the smallest number of roubles you have to pay in order to buy at least L liters of lemonade.

Example

Input

4 12
20 30 70 90

Output

Input

4 3
10000 1000 100 10

Output

Input

4 3
10 100 1000 10000

Output

Input

5 787787787
123456789 234567890 345678901 456789012 987654321

Output

44981600785557577

Note

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.

In the second example, even though you need only 3 liters, it's cheaper to buy a single 8-liter bottle for 10 roubles.

In the third example it's best to buy three 1-liter bottles for 10 roubles each, getting three liters for 30 roubles.

题意：给你 n 个物品，以及一个容器的体积 l , n 个物品的体积是 2^i-1 ，求在超过容器体积的前提下，最小的花费是多少。

思路分析：想了一个贪心策略，优先去贪性价比最高的物品，当恰好装下的时候，此时可以记录一下答案，若不能时，此时可以让他们多装一个，再次记录一下答案，深搜就行了

代码示例：

/*

 * Author:  parasol

 * Created Time:  2018/3/7 18:18:10

 * File Name: 2.cpp

 */

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <map>

#include <time.h>

using namespace std;

#define ll long long

const ll maxn = 1e6+5;

const double pi = acos(-1.0);

const ll inf = 0x3f3f3f3f;

struct node

{

    ll l, c;

    double p;

    bool operator< (const node &v)const{

        return p < v.p;

    }

}pre[35];

ll n, l;

ll ans = __LONG_LONG_MAX__;

void dfs(ll x, ll cost, ll sum){

    if (cost >= ans) return;

    if (sum <= 0) {ans = min(ans, cost); return;}

    if (x == n+1) return;

    ll f = sum / pre[x].l;

    int pt = 0;

    if (sum%pre[x].l == 0){

        ans = min(ans, cost+f*pre[x].c);

        return;

    }

    else {

        dfs(x+1, cost+(f+1)*pre[x].c, sum-(f+1)*pre[x].l);

        pt = 1;

    }

    if (pt) {

        dfs(x+1, cost+f*pre[x].c, sum-f*pre[x].l);

    }

}

int main() {

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    cin >> n >> l;

    ll an = 1;

    for(ll i = 1; i <= n; i++){

        scanf("%lld", &pre[i].c);

        pre[i].l = an;

        pre[i].p = 1.0*pre[i].c/an;

        an *= 2;

    }

    sort(pre+1, pre+1+n);

    dfs(1, 0, l);

    printf("%lld\n", ans);

    return 0;

}

巴特西

贪心 + DFS

最新文章

热门文章