stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 2.990247930756549x):
#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]);

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 3.1337074270881304x):
#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]);

 }
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 3.1144425141818157x):
#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]);

 }
// Slower C++ solution:
#include <iostream>

#include <sstream>

#include <string>

#include <algorithm>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <map>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <cassert>



using namespace std;



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

#define REP(i,n) FOR(i,0,n)

#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)



template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }

inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }



typedef long long ll;

const int INF = 100000000;

const double EPS = 1e-8;

const int MOD = 1000000007;

int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};

int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};



const int MAX = 300;



int main(){

  int S, D, M;

  while(cin >> S >> D >> M){

    int dp[100][MAX + 1] = {};

    REP(i, S){

      int K;

      cin >> K;

      while(K--){

        int w, p;

        cin >> w >> p;

        for(int y = MAX; y >= 0; y--){

          if(y - p >= 0) dp[i][y] = max(dp[i][y], dp[i][y - p] + w);

        }

      }

    }

    int ans[MAX + 1] = {};

    REP(i, D){

      int f; cin >> f;

      for(int j = MAX; j >= 0; j--){

        for(int k = 0; j - k >= 0; k++){

          ans[j] = max(ans[j], ans[j - k] + dp[f][k]);

        }

      }

    }

    while(M > 0 && ans[M] == ans[M - 1]) M--;

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

  }

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.319315576884193x):
#include <iostream>

#include <sstream>

#include <string>

#include <algorithm>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <map>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <cassert>



using namespace std;



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

#define REP(i,n) FOR(i,0,n)

#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)



template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }

inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }



typedef long long ll;

const int INF = 100000000;

const double EPS = 1e-8;

const int MOD = 1000000007;

int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};

int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};



const int MAX = 300;



int main(){

  int S, D, M;

  while(cin >> S >> D >> M){

    int dp[100][MAX + 1] = {};

    REP(i, S){

      int K;

      cin >> K;

      while(K--){

        int w, p;

        cin >> w >> p;

        for(int y = M; y >= 0; y--){

          if(y - p >= 0) dp[i][y] = max(dp[i][y], dp[i][y - p] + w);

        }

      }

    }

    int ans[MAX + 1] = {};

    REP(i, D){

      int f; cin >> f;

      for(int j = M; j >= 0; j--){

        for(int k = 0; j - k >= 0; k++){

          ans[j] = max(ans[j], ans[j - k] + dp[f][k]);

        }

      }

    }

    while(M > 0 && ans[M] == ans[M - 1]) M--;

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

  }

  return 0;

}
// Slower C++ solution:
#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;

  }

}

// Faster C++ solution for the same problem (measured speedup: 5.1158380419164065x):
#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);

  }

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 4.4956725209118x):
#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;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 3.4577412830222283x):
#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;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 1.8003745567394291x):
#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;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 1.1016033735826172x):
#include <queue>

#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long LL;



int n, m;

LL ans;



priority_queue <int> Q;



int main()

{

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

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

	{

		scanf("%d", &x);

		Q.push(x);

	}

	while (m --)

	{

		int t = Q.top();

		Q.pop();

		Q.push(t / 2);

	}

	while (!Q.empty())

	{

		ans += Q.top();

		Q.pop();

	}

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

	return 0;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 5.251328851644183x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 5.299833167819966x):
#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;

}
// Slower C++ solution:
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

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

#define mod 1000000007

typedef long long ll;

using namespace std;

ll n,m;

priority_queue<ll>q;

int main()

{

    abdelrahman001

    cin >> n >> m;

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

        cin >> x,q.push(x);

    while(m--)

    {

        ll x = q.top();

        q.pop();

        q.push(x/2);

    }

    ll ans = 0;

    while(!q.empty())

        ans+=q.top(),q.pop();

    cout << ans;

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.344977993351092x):
#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;

}