stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
/*Lucky_Glass*/

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<cmath>

#include<vector>

#include<queue>

using namespace std;

const int MAXN=1e5;

struct EDGE{

	int v,val[2];

	EDGE(){}

	EDGE(int c,int d,int e){v=c;val[0]=d;val[1]=e;}

};

int n_cty,n_edg,s,t;

vector<EDGE>lnk[MAXN+5];

long long dist[2][MAXN+5],ans[MAXN+5];//0:yen start->i   1:snuuk end->i

bool vis[MAXN+5];

void SPFA(int start,int kind)

{

	memset(vis,0,sizeof vis);

	fill(dist[kind],dist[kind]+n_cty+3,1e15);

	queue<int> que;que.push(start);

	dist[kind][start]=0;vis[start]=true;

	while(!que.empty())

	{

		int u=que.front();que.pop();

		for(int i=0;i<lnk[u].size();i++)

		{

			int v=lnk[u][i].v,val=lnk[u][i].val[kind];

			if(dist[kind][v]>dist[kind][u]+val)

			{

				dist[kind][v]=dist[kind][u]+val;

				if(!vis[v])

					vis[v]=true,que.push(v);

			}

		}

		vis[u]=false;

	}

}

struct DEQUE{

	int val,date;

	DEQUE(){}

	DEQUE(int a,int b){val=a;date=b;}

};

int main()

{

	scanf("%d%d%d%d",&n_cty,&n_edg,&s,&t);

	for(int i=0;i<n_edg;i++)

	{

		int u,v,a,b;scanf("%d%d%d%d",&u,&v,&a,&b);

		lnk[u].push_back(EDGE(v,a,b));

		lnk[v].push_back(EDGE(u,a,b));

	}

	SPFA(s,0);

	SPFA(t,1);

	fill(ans+1,ans+n_cty+3,1e15);

	for(int i=n_cty;i>=1;i--)

	{

		long long val=dist[0][i]+dist[1][i];

		ans[i]=min(ans[i+1],val);

	}

	for(int i=1;i<=n_cty;i++)

		printf("%lld\n",(long long)1e15-ans[i]);

	/*

	deque<DEQUE> low;

	for(int i=1;i<=n_cty;i++)

	{

		int val=dist[0][i]+dist[1][i];

		while(!low.empty() && low.back().val>val) low.pop_back();

		low.push_back(DEQUE(val,i));

	}

	for(int i=1;i<=n_cty;i++)

	{

		while(!low.empty() && low.front().date<i) low.pop_front();

		printf("%lld\n",(long long)1e15-low.front().val);

	}

	*/

	return 0;

}


// Optimized solution to the same problem (faster):
//SPFA

#include<bits/stdc++.h>

#define ll long long

#define INF 1e18

#define MAXN 100005



ll min(ll x,ll y){if(x<y) return x;return y;}

	

	int n,m,s,t,u,v;

	ll a,b,f=1e15,ans[MAXN];

	

struct Graph

{

	int cnt,head[MAXN],vis[MAXN];

	ll dis[MAXN];

	

	struct Edge{int next,to;ll dis;}edge[MAXN*2];

	

	std::queue<int> q;

	

	void addedge(int from,int to,ll dis)

	{

		edge[++cnt].next=head[from];

		edge[cnt].to=to;

		edge[cnt].dis=dis;

		head[from]=cnt;

	}

	void spfa(int s)

	{

		for(int i=1;i<=n;i++) dis[i]=INF;

		memset(vis,0,sizeof(vis));

		q.push(s);vis[s]=1;dis[s]=0;

		while(!q.empty())

		{

			int x=q.front();q.pop();

			vis[x]=0;

			for(int i=head[x];i;i=edge[i].next)

			{

				int to=edge[i].to;

				if(dis[to]>dis[x]+edge[i].dis)

				{

					dis[to]=dis[x]+edge[i].dis;

					if(!vis[to]) q.push(to),vis[to]=1;

				}

			}

		}

	}

}g1,g2;



int main()

{

	scanf("%d%d%d%d",&n,&m,&s,&t);

	for(int i=1;i<=m;i++)

	{

		scanf("%d%d%lld%lld",&u,&v,&a,&b);

		g1.addedge(u,v,a);g1.addedge(v,u,a);

		g2.addedge(v,u,b);g2.addedge(u,v,b);

	}

	g1.spfa(s);g2.spfa(t);

	ans[n+1]=INF;

	for(int i=n;i>=1;i--) ans[i]=min(ans[i+1],g1.dis[i]+g2.dis[i]);

	for(int i=1;i<=n;i++) printf("%lld\n",f-ans[i]);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<vector>

#include<queue>



using namespace std;

#define int long long

using P = pair<int,int>;

int N,M,S,T;

struct edge{int to,idx;};//行先とindex

vector<edge> G[101000];//グラフ,二次元配列っぽくあつかってる？

vector<int> A(101000),B(101000);//円とすぬけ



vector<int> dijkstra(int s,vector<int>& cost){

    vector<int> dist(101000,1e18); dist[s] = 0;//距離を無限に

    priority_queue<P,vector<P>,greater<P>> Q;

    Q.push({0,s});



    while(!Q.empty()){

        P p = Q.top(); Q.pop();

        if(dist[p.second] < p.first) continue;

        for(auto & e : G[p.second]){

            if(dist[e.to] > dist[p.second] + cost[e.idx]){

                dist[e.to] = dist[p.second] + cost[e.idx];

                Q.push({dist[e.to],e.to});

            }

        }

    }

    return dist;

}

signed main(){

    cin>>N>>M>>S>>T;

    for(int i=0;i<M;++i){

        int u,v;

        cin>>u>>v>>A[i]>>B[i];

        G[u].push_back({v,i});//駅uからつながるvと年i

        G[v].push_back({u,i});//駅vからつながる

    }



    auto yen = dijkstra(S,A);

    auto snuke = dijkstra(T,B);



    int ans = 0;

    vector<int> res;

    int base = 1e15;

    for(int i=N;i>0;--i){

        ans = max(ans,base - yen[i] - snuke[i]);

        res.push_back(ans);

    }



    for(int i = res.size()-1;i>=0;--i) cout<<res[i]<<endl;



}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

#define int long long

using P = pair<int,int>;



struct edge{int to,idx;};

vector<edge> G[100100];



vector<int> dijkstra(int s,vector<int>& cost){

    vector<int> dist(100100,1e18); dist[s] = 0;

    priority_queue<P,vector<P>,greater<P>> Q;

    Q.push({0,s});

    while(!Q.empty()){

        P p = Q.top(); Q.pop();

        if(dist[p.second] < p.first) continue;

        for(auto &e : G[p.second]){

            if(dist[e.to] > dist[p.second] + cost[e.idx]){

                dist[e.to] = dist[p.second] + cost[e.idx];

                Q.push({dist[e.to],e.to});

            }

        }

    }

    return dist;

}



signed main(){

    int N,M,S,T;

    cin>>N>>M>>S>>T;

    vector<int> A(M),B(M);

    for(int i=0;i<M;++i){

        int u,v; cin>>u>>v>>A[i]>>B[i];

        G[u].push_back({v,i});

        G[v].push_back({u,i});

    }



    auto yen = dijkstra(S,A);

    auto snuuk = dijkstra(T,B);



    int ans = 0;

    vector<int> res;



    for(int i=N;i>0;--i){

        ans = max(ans,(int)1e15-yen[i]-snuuk[i]);

        res.push_back(ans);

    }



    for(int i=N-1;i>=0;--i) cout<<res[i]<<endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<algorithm>

using namespace std;



#define MAXN 100000

int N,M;

struct Edge{

    int v,w[2];

    Edge(){}

    Edge(int a,int w1,int w2){

        v=a,w[0]=w1,w[1]=w2;

    }

};

vector<Edge> G[MAXN+5];



bool vis[MAXN+5];

long long dist[2][MAXN+5];

void SPFA(int S,int opt){

    memset(vis,0,sizeof vis);

    memset(dist[opt],0x3f,sizeof dist[opt]);

    queue<int> Q;Q.push(S);

    dist[opt][S]=0;vis[S]=1;

    while(!Q.empty()){

        int u=Q.front();

        vis[u]=0;Q.pop();

        for(int i=0;i<int(G[u].size());i++){

            int v=G[u][i].v,w=G[u][i].w[opt];

            if(dist[opt][v]>dist[opt][u]+w){

                dist[opt][v]=dist[opt][u]+w;

                if(!vis[v]){

                    vis[v]=1;

                    Q.push(v);

                }

            }

        }

    }

}



long long Ans[MAXN+5];

int main(){

    int S,T;

    scanf("%d%d%d%d",&N,&M,&S,&T);

    for(int i=1;i<=M;i++){

        int u,v,w1,w2;

        scanf("%d%d%d%d",&u,&v,&w1,&w2);

        G[u].push_back(Edge(v,w1,w2));

        G[v].push_back(Edge(u,w1,w2));

    }

    SPFA(S,0);

    SPFA(T,1);

    Ans[N]=dist[0][N]+dist[1][N];

    for(int i=N-1;i>=1;i--)

        Ans[i]=min(Ans[i+1],dist[0][i]+dist[1][i]);

    for(int i=1;i<=N;i++)

        printf("%lld\n",1000000000000000ll-Ans[i]);

    return 0;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

#define INF 1e18

#define N 100005

int n,m,s,t;

long long f=1e15;

long long ans[N];

struct node//学到老，回到老

{

	struct Edge

	{

		int next;

		int to;

		long long dis;

	}edge[N*2+5];

	

	int cnt;

	int head[N*2],vis[N];

	long long dis[N];

	void add(int from,int to,long long dis)

	{

		edge[++cnt].next=head[from];

		edge[cnt].to=to;

		edge[cnt].dis=dis;

		head[from]=cnt;

	}

	

	queue<int >Q;

	

	void SPFA(int s)

	{

		for(int i=1;i<=n;i++)

		dis[i]=INF;

		memset(vis,0,sizeof vis);

		Q.push(s);

		vis[s]=1;

		dis[s]=0;

		while(!Q.empty())

		{

			int x=Q.front();

			Q.pop();

			vis[x]=0;

			for(int i=head[x];i;i=edge[i].next)

			{

				int to=edge[i].to;

				if(dis[to]>dis[x]+edge[i].dis)

				{

					dis[to]=dis[x]+edge[i].dis;

					if(!vis[to]) Q.push(to),vis[to]=1;

				}

			}

		}

	}

}G1,G2;

int main()

{

	scanf("%d %d %d %d",&n,&m,&s,&t);

	int u,v;

	long long a,b;

	for(int i=1;i<=m;i++)

	{

		scanf("%d %d %lld %lld",&u,&v,&a,&b);

		G1.add(u,v,a);

		G1.add(v,u,a);

		G2.add(u,v,b);

		G2.add(v,u,b);

	}

	G1.SPFA(s);

	G2.SPFA(t);

	ans[n+1]=INF;

	for(int i=n;i>=1;i--)

	ans[i]=min(ans[i+1],G1.dis[i]+G2.dis[i]);

	for(int i=1;i<=n;i++)

	printf("%lld\n",f-ans[i]);

 } 

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<queue>

#include<vector>

#include<cstring>

#include<algorithm>

using namespace std;

const int Maxn=1e5;

const long long Tot=1e15;

typedef long long ll;

struct Edge {

	int v;

	ll m[2];

	Edge(int a,int b,int c) {v=a,m[0]=b,m[1]=c;}

};

vector<Edge> G[Maxn+5];

void AddEdge(int u,int v,int x,int y) {

	G[u].push_back(Edge(v,x,y));

	G[v].push_back(Edge(u,x,y));

}

ll dist[2][Maxn+5];

bool vis[Maxn+5];

void SPFA(int s,int ty) {

	queue<int> q;

	memset(vis,0,sizeof vis);

	memset(dist[ty],0x3f,sizeof dist[ty]);

	

	q.push(s);

	vis[s]=true;dist[ty][s]=0;

	

	while(!q.empty()) {

		int u=q.front();

		q.pop();vis[u]=false;

		

		for(int i=0;i<G[u].size();i++) {

			int v=G[u][i].v,w=G[u][i].m[ty];

			if(dist[ty][v]>dist[ty][u]+w) {

				dist[ty][v]=dist[ty][u]+w;

				if(!vis[v]) {

					vis[v]=true;

					q.push(v);

				}

			}

		}

	}

}

int N,M,S,T;

ll ans[Maxn+5];

int main() {

	#ifdef LOACL

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

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

	#endif

	scanf("%d %d %d %d",&N,&M,&S,&T);

	for(int i=1;i<=M;i++) {

		int u,v,x,y;

		scanf("%d %d %d %d",&u,&v,&x,&y);

		AddEdge(u,v,x,y);

	}

	SPFA(S,0);

	SPFA(T,1);

	ans[N]=dist[0][N]+dist[1][N];

	for(int i=N-1;i>=1;i--)

		ans[i]=min(ans[i+1],dist[0][i]+dist[1][i]);

	for(int i=1;i<=N;i++)

		printf("%lld\n",Tot-ans[i]);

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

#define INF 1e18

#define N 100005

int n,m,s,t;

long long f=1e15;

long long ans[N];

struct node//学到老，回到老

{

	struct Edge

	{

		int next;

		int to;

		long long dis;

	}edge[N*2+5];

	

	int cnt;

	int head[N*2],vis[N];

	long long dis[N];

	void add(int from,int to,long long dis)

	{

		edge[++cnt].next=head[from];

		edge[cnt].to=to;

		edge[cnt].dis=dis;

		head[from]=cnt;

	}

	

	queue<int >Q;

	

	void SPFA(int s)

	{

		for(int i=1;i<=n;i++)

		dis[i]=INF;

		memset(vis,0,sizeof vis);

		Q.push(s);

		vis[s]=1;

		dis[s]=0;

		while(!Q.empty())

		{

			int x=Q.front();

			Q.pop();

			vis[x]=0;

			for(int i=head[x];i;i=edge[i].next)

			{

				int to=edge[i].to;

				if(dis[to]>dis[x]+edge[i].dis)

				{

					dis[to]=dis[x]+edge[i].dis;

					if(!vis[to]) Q.push(to),vis[to]=1;

				}

			}

		}

	}

}G1,G2;

int main()

{

	scanf("%d %d %d %d",&n,&m,&s,&t);

	int u,v;

	long long a,b;

	for(int i=1;i<=m;i++)

	{

		scanf("%d %d %lld %lld",&u,&v,&a,&b);

		G1.add(u,v,a);

		G1.add(v,u,a);

		G2.add(u,v,b);

		G2.add(v,u,b);

	}

	G1.SPFA(s);

	G2.SPFA(t);

	ans[n+1]=INF;

	for(int i=n;i>=1;i--)

	ans[i]=min(ans[i+1],G1.dis[i]+G2.dis[i]);

	for(int i=1;i<=n;i++)

	printf("%lld\n",f-ans[i]);

 } 

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<algorithm>

using namespace std;



int dp[330];

int s,d,m;

int k[110],w[110][55],p[110][55],f[110];



int main(){

  

  while(cin >> s >> d >> m){

    for(int i=0;i<s;i++){

      cin >> k[i];

      for(int j=0;j<k[i];j++)cin >> w[i][j] >> p[i][j];

    }

    for(int i=0;i<d;i++)cin >> f[i];



    for(int i=0;i<=m;i++)dp[i] = -1;

    

    dp[0] = 0;



    for(int i=0;i<d;i++){

      for(int x=0;x<k[f[i]];x++){

	int v = p[f[i]][x], c = w[f[i]][x];

	for(int j=m-v;j>=0;j--){

	  if(dp[j]>=0)dp[j+v] = max(dp[j+v],dp[j]+c);

	}

      }

    }

	

    int ans = 0;

    for(int i=1;i<=m;i++)

      if(dp[i] > dp[ans])ans = i;

    cout << dp[ans] << " " << ans << endl;

  }

}

// Optimized solution to the same problem (faster):
#include<cstdio>

using namespace std;



int dp[330];

int s,d,m;

int k[110],w[110][55],p[110][55],f;



int main(){

  while(scanf("%d%d%d",&s,&d,&m)!=EOF){

    for(int i=0;i<s;i++){

      scanf("%d",&k[i]);

      for(int j=0;j<k[i];j++)scanf("%d%d",&w[i][j],&p[i][j]);

    }



    for(int i=0;i<=m;i++)dp[i] = -1;

    dp[0] = 0;



    for(int i=0;i<d;i++){

      scanf("%d",&f);

      for(int x=0;x<k[f];x++){

	int v = p[f][x], c = w[f][x];

	for(int j=m-v;j>=0;j--){

	  if(dp[j]>=0 && dp[j+v]<dp[j]+c)dp[j+v] = dp[j]+c;

	}

      }

    }

	

    int ans = 0;

    for(int i=1;i<=m;i++)

      if(dp[i] > dp[ans])ans = i;

    printf("%d %d\n",dp[ans],ans);

  }

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cmath>

#include <string>

#include <algorithm>

#include <vector>

using namespace std;



int main(void){

    string s, t;

    cin >> s; cin >> t;

    int count = 0;

    int check = 0;

    vector<string> ans(100000);

    if(s.length()>=t.length()){

    for(int i = 0; i <= s.length()-t.length(); i++){

        count = 0;

        for(int j = 0; j < t.length(); j++){

            if(s[i+j]==t[j]||s[i+j]=='?') count++;

        }

        if(count==t.length()){

            ans[check].insert(0, s, 0, i);

            ans[check]+=t;

            ans[check].insert(i+t.length(), s, i+t.length(), s.length()-t.length()-i);

            check++;

        }

    }}

    if(check==0)

        cout << "UNRESTORABLE" << endl;

    else{

        for(int i = 0; i < check; i++){

            for(int j = 0; j < ans[i].length(); j++){

                if(ans[i][j]=='?') 

                    ans[i][j]='a';

            }

        }

        sort(&ans[0], &ans[check]);

        cout << ans[0] << endl;

    }

    return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

#include <string>

#include <queue>

#include <utility>

#include <map>

#include <bitset>

#include <numeric>

#define ll long long

using namespace std;

using p = pair<ll, ll>;

ll dx[8]={ 0, 1, 0,-1, 1, 1,-1,-1}; // x軸方向への変位

ll dy[8]={ 1, 0,-1, 0, 1,-1, 1,-1}; // y軸方向への変位



int main(void) {

    string s, t;

    cin >> s >> t;

    ll count = 0;

    ll len = 0;

    bool ok = false;

    ll c = 0;

    if(s.length()>=t.length()){

        for(ll i = 0; i <= s.length()-t.length(); i++){

            //cout << i << endl;

            for(ll j = 0; j < t.length(); j++){

                if(s[i+j]!=t[j] && s[i+j]!='?') break;

                if(j==t.length()-1) {

                    ok = true;

                    c = i;

                }

            }

        }

    }

    string ans;

    if(ok==true){

        for(ll i = 0; i < c; i++) {

            if(s[i]!='?')ans += s[i];

            else ans+= 'a';



        }

        ans += t;

        for(ll i = c+t.length(); i < s.length(); i++){

            if(s[i]!='?')ans += s[i];

            else ans+= 'a';

        }

        cout << ans << endl;

    }

    else if(ok==false)

        cout << "UNRESTORABLE" << endl;

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <bits/stdc++.h>

#define pb push_back

#define ob pop_back

#define xx first

#define yy second

#define dob double

#define rin(i,n,k) for(int i=0;i<n;i+=k)

#define int long long int

#define ss size()

using namespace std;

const int M=1e9+7,maxn=100010;

std::vector<int> adj[maxn];

std::vector<int> v1;

int ans,n,k,m,x,y,q,par[maxn],h[maxn],mach[maxn],sk[maxn],dp[maxn];

bool mark[maxn],bpart[maxn];

string s,s1,s2;

map <string ,int> mp;

bool markchaild[maxn];



int32_t main() {

    cin>>s;

    q=753;

    for(int i=2;i<s.ss;i++){

        ans=(s[i-2]-'0')*100;

        ans+=(s[i-1]-'0')*10;

        ans+=(s[i]-'0');

        //cout<<ans<<endl;

        ans=fabs(ans-753);

        if(ans<q)

            q=ans;

    }

    cout<<q;

    return 0;

}


// Optimized solution to the same problem (faster):
#include <iostream>

#include <vector>

#include <algorithm>

#include <string>

#include <sstream>

using namespace std;

pair<int,long long>p[100006];

int main() {

    string s;

    cin>>s;

    int ans=1000;

    for(int i=0;i<s.size()-2;i++)

    {

        string g="";

        g=s.substr(i,3);

        stringstream a(g);

        int b=0;

        a >> b;

        ans=min(ans,abs(753-b));

    }

    cout<<ans;

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<algorithm>

#include<vector>

using lint=int64_t;

using namespace std;



int main()

{

	int N,M;

	lint A[100010]={};

	lint sum=0;



	cin >> N >> M;

	for(int i=0;i<N;i++)

	{

		cin >> A[i];

		sum+=A[i];

	}



	vector<int> v;

	for(int i=0;i<N;i++)

	{

		while(A[i]>0)

		{

			v.push_back(A[i]-A[i]/2);

			A[i]/=2;

		}

	}



	sort(v.begin(),v.end(),greater<int>());



	lint ans=0;

	for(int i=0;i<(int)v.size() && i<M;i++)

		ans+=v[i];



	cout << max((lint)0,sum-ans) << endl;

	return 0;

}


// Optimized solution to the same problem (faster):
#include<iostream>

#include<algorithm>

#include<queue>

using lint=int64_t;

using namespace std;



int main()

{

	int N,M;

	priority_queue<lint> que;



	cin >> N >> M;

	for(int i=0;i<N;i++)

	{

		lint A;

		cin >> A;

		que.push(A);

	}

	

	for(int i=0;i<M;i++)

	{

		lint tmp=que.top();

		que.pop();

		que.push(tmp/2);

	}



	lint ans=0;

	while(!que.empty())

	{

		ans+=que.top();

		que.pop();

	}



	cout << ans << endl;

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define f first

#define s second



using namespace std;



typedef long long ll;



int main(){

    ios_base::sync_with_stdio(0); cin.tie(0);

    int n, m; cin >> n >> m;

    priority_queue <ll> nums;

    for(int i=0; i<n; i++){

        ll tmp; cin >> tmp;

        nums.push(tmp);

    }

    while(m--){

        ll tmp = nums.top();

        nums.pop();

        nums.push(tmp/2);

    }

    ll ans = 0;

    while(!nums.empty()){

        ans += nums.top();

        nums.pop();

    }

    cout << ans << '\n';

    return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>



typedef long long LL;



const int MAXN=100005;



void fix_down(int *h,int i,int n)

{

    int j=i,k,t=h[i];

    while ((j<<1)+1<n)

    {

        k=(j<<1)+1;

        if (k+1<n&&h[k+1]>h[k]) k=k+1;

        if (t>=h[k]) break;

        h[j]=h[k];

        j=k;

    }

    h[j]=t;

}



int main()

{

    int N,M,t;

    LL ans=0LL;

    static int h[MAXN];



    scanf("%d%d",&N,&M);

    for (int i=0;i<N;++i)

        scanf("%d",&h[i]);



    for (int i=N-1;i>=0;--i)

        fix_down(h,i,N);

    for (int i=0;i<M;++i)

    {

        if (h[0]==0) break;

        h[0]=h[0]>>1;

        fix_down(h,0,N);

    }

    for (int i=0;i<N;++i)

        ans=ans+h[i];

    printf("%lld",ans);



    return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<stdlib.h>

#include<string.h>

#include<cmath>

#include<queue>

using namespace std;

typedef long long ll;

#define N 100005

int main()

{

    int n,m,i,j,k,l;

    int T,unit;

    int x,z,y,x1,y1;

    ll ans1=0,ans2=0;

    int n1,n2;

    int a[100005]={0};

    priority_queue<int> q;

    cin>>n>>m;

    for(i=0;i<n;i++)

    {

        scanf("%d",&x);

        q.push(x);

    }

    for(i=0;i<m;i++)

    {

        y=q.top();

        q.pop();

        q.push(y/2);

    }

    while(!q.empty())

    {

        ans1+=q.top();

        q.pop();

    }

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

    return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>



typedef long long LL;



const int MAXN=100005;



void fix_down(int *h,int i,int n)

{

    int j=i,k,t=h[i];

    while ((j<<1)+1<n)

    {

        k=(j<<1)+1;

        if (k+1<n&&h[k+1]>h[k]) k=k+1;

        if (t>=h[k]) break;

        h[j]=h[k];

        j=k;

    }

    h[j]=t;

}



int main()

{

    int N,M,t;

    LL ans=0LL;

    static int h[MAXN];



    scanf("%d%d",&N,&M);

    for (int i=0;i<N;++i)

        scanf("%d",&h[i]);



    for (int i=N-1;i>=0;--i)

        fix_down(h,i,N);

    for (int i=0;i<M;++i)

    {

        if (h[0]==0) break;

        h[0]=h[0]>>1;

        fix_down(h,0,N);

    }

    for (int i=0;i<N;++i)

        ans=ans+h[i];

    printf("%lld",ans);



    return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cmath>

#include<stdio.h>

#include <ctype.h>

#include<iomanip>

#include<algorithm>

#include<string>

#include<stack>

#include<set>

#include<map>

#include<deque> //<< fixed << setprecision()

#include<queue> //priority_queue

#include<vector>

#define em3 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#define iof freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);



using namespace std;

#define f first

#define s second

#define X real()

#define Y imag()

#define cross(a, b) ((conj(a) * (b)).Y)

#define dot(a, b) ((conj(a) * (b)).X)

#define inFile(t) freopen((t),"r",stdin)

#define outFile(t) freopen((t),"w",stdout)

#define all(v) (v).begin(),(v).end()

#define allr(v) (v).rbegin(),(v).rend()

#define EPS 1e-7

long long mod = 1e9 + 7;

const int N = 1e4 + 5;

typedef long long ll;

typedef unsigned long long ull;

typedef long double ld;

const double pi = acos(-1);

//typedef complex <ll> point;

typedef tuple<int, int, int> line;

//typedef vector<point> polygon;





int main()

{

	priority_queue<ll>q;

	ll n, m;

	cin >> n >> m;

	for (int i = 0; i < n; i++)

	{

		ll x;

		cin >> x;

		q.push(x);

	}

	for (int i = 0; i < m; i++)

	{

		ll x = q.top();

		q.pop();

		q.push(x / 2);

	}

	ll sum = 0;

	for (; q.size();)

	{

		sum += q.top();

		q.pop();

	}

	cout << sum;

}

// Optimized solution to the same problem (faster):
#include <cstdio>



typedef long long LL;



const int MAXN=100005;



void fix_down(int *h,int i,int n)

{

    int j=i,k,t=h[i];

    while ((j<<1)+1<n)

    {

        k=(j<<1)+1;

        if (k+1<n&&h[k+1]>h[k]) k=k+1;

        if (t>=h[k]) break;

        h[j]=h[k];

        j=k;

    }

    h[j]=t;

}



int main()

{

    int N,M,t;

    LL ans=0LL;

    static int h[MAXN];



    scanf("%d%d",&N,&M);

    for (int i=0;i<N;++i)

        scanf("%d",&h[i]);



    for (int i=N-1;i>=0;--i)

        fix_down(h,i,N);

    for (int i=0;i<M;++i)

    {

        if (h[0]==0) break;

        h[0]=h[0]>>1;

        fix_down(h,0,N);

    }

    for (int i=0;i<N;++i)

        ans=ans+h[i];

    printf("%lld",ans);



    return 0;

}




// Fastest known solution for this problem: