cf913C(貪心)

這次題目還是出得有水準的，考的不是手速了，而是思維，另外也不會讓人感受到有心無力。。還暴露了自己一些嚴重的問題，總的來說土神就是土神

好久沒寫過貪心了，貌似高中也沒怎麼寫過，遇到了也是想了蠻久才想出最優政策。。

按機關價格把排序，怕單價會有精度問題就直接轉除為乘了。。然後依次往總容量裡面填，讓單價小的盡量填，然後一般會出現填不滿的情況，試着再加一個目前的罐子，加上目前的已用的費用來找出最優解

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define eps 1e-8
#define inf (ll)1000000000000000000
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define succ(x) (1<<x)
#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define ls T[i<<1]
#define rs T[i<<1|1]
#define op T[i]
#define NM 50005
#define nm 100005
#define pi 3.141592653
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f*x;
}




int n,m,a[NM],tmp[NM];
ll b[NM],c[NM],t,ans,_ans=inf;
bool cmp(int x,int y){return c[x]<c[y];}
int main(){
    n=read();m=read();
    b[1]=1;
    inc(i,2,n)b[i]=b[i-1]*2;
    inc(i,1,n)a[i]=read();
    inc(i,1,n)c[i]=a[i]*b[n-i+1];
    inc(i,1,n)tmp[i]=i;
    sort(tmp+1,tmp+1+n,cmp);
    for(int k=1,i=tmp[k];k<=n;i=tmp[++k]){
        t=m/b[i];
        m-=b[i]*t;
        ans+=t*a[i];
        if(m==0){
            _ans=min(_ans,ans);
        }else{
            _ans=min(_ans,ans+a[i]);
        }
    }
    printf("%I64d\n",_ans);
    return 0;
}      

C. Party Lemonade

time limit per test

memory limit per test

input

output

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 2i - 1 liters and costs ci

You want to buy at least L

Input

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.

The second line contains n integers c1, c2, ..., cn (1 ≤ ci ≤ 109) — 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

Examples

Input

4 12

20 30 70 90

Output

150

Input

4 3

10000 1000 100 10

Output

10

Input

4 3

10 100 1000 10000

Output

30

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.