stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>



using namespace std;

using namespace __gnu_pbds;

 

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define fbo find_by_order

#define ook order_of_key

 

typedef long long ll;

typedef pair<int,ll> ii;

typedef vector<int> vi;

typedef long double ld; 

typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

typedef set<ll>::iterator sit;

typedef map<ll,ll>::iterator mit;



int siz[111111];

vector<ii> adj[111111];



void prep(int u, int p)

{

	siz[u]=1;

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

	{

		int v=adj[u][i].fi;

		if(v==p) continue;

		prep(v,u);

		siz[u]+=siz[v];

	}

}

int n;

int centroid(int u, int p)

{

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

	{

		int v=adj[u][i].fi;

		if(v==p) continue;

		if(siz[v]*2>n)

		{

			return centroid(v,u);

		}

	}

	return u;

}



ll ans=0;



void solve(int u, int p)

{

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

	{

		int v=adj[u][i].fi; ll w=adj[u][i].se;

		if(v==p) continue;

		ans+=ll(2)*siz[v]*w;

		//cerr<<u<<' '<<v<<' '<<w<<' '<<2*siz[v]<<'\n';

		solve(v,u);

	}

}



int main()

{

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

	cin>>n;

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

	{

		int u,v,w;

		cin>>u>>v>>w;

		u--; v--;

		adj[u].pb(mp(v,w));

		adj[v].pb(mp(u,w));

	}

	prep(0,-1);

	int cent = centroid(0,-1);

	prep(cent,-1);

	ll mini=ll(1e18);

	for(int i=0;i<adj[cent].size();i++)

	{

		int v=adj[cent][i].fi; ll w=adj[cent][i].se;

		if(siz[v]>=(n+1)/2)

		{

			mini=w;

			break;

		}

		mini=min(mini,w);

	}

	ans-=mini;

	solve(cent,-1);

	cout<<ans<<'\n';

}


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

using namespace std;

#define MN 100005

#define inf 0x3f3f3f3f

inline int read(){

	int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x*f;

}

struct edge{int t,nex,w;}e[MN*2];int hr[MN],cnt;

void ins(int f,int t,int w){e[++cnt]=(edge){t,hr[f],w};hr[f]=cnt;}

int n,a,b,c,dind,l[MN],r[MN],sons[MN],mson[MN],mins=inf,mid;

long long ans;

void dfs(int x,int fa,int w){

	l[x]=++dind;int maxi=0;

	for(int i=hr[x];i;i=e[i].nex)

		if(e[i].t!=fa){

			dfs(e[i].t,x,e[i].w);

			sons[x]+=sons[e[i].t]+1;

			maxi=max(maxi,sons[e[i].t]+1);

	}

	r[x]=dind;

	int mini=min(r[x]-l[x]+1,n-r[x]+l[x]-1);

	ans+=(long long) mini*w*2;

	maxi=max(maxi,n-1-sons[x]);

	mson[x]=maxi;

	if(maxi<mins) mins=maxi,mid=x;

}

int main(){

	n=read();register int i;

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

		a=read(),b=read(),c=read();

		ins(a,b,c);ins(b,a,c);

	}

	dfs(1,0,0);int lowe=inf;

	for(i=hr[mid];i;i=e[i].nex){

		lowe=min(lowe,e[i].w);

		if(mson[e[i].t]==mson[mid]){

			printf("%lld\n",ans-e[i].w);

			return 0;

		}

	}

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

	return 0;

}

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

#define INF 0x3f3f3f3f

#define maxn 500100

#define lson root << 1

#define rson root << 1 | 1

#define lent (t[root].r - t[root].l + 1)

#define lenl (t[lson].r - t[lson].l + 1)

#define lenr (t[rson].r - t[rson].l + 1)

#define N 1111

#define eps 1e-6

#define pi acos(-1.0)

#define e exp(1.0)

using namespace std;

const int mod = 1e9 + 7;

typedef long long ll;

typedef unsigned long long ull;

char s[maxn];

int a[maxn];

int len;

bool check(int x)

{

    int sum = x * 9, cnt = 0;

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

    {

        sum += a[i];

        cnt += sum % 10;

        sum /= 10;

    }

    while (sum > 0)

    {

        cnt += sum % 10;

        sum /= 10;

    }

    return cnt <= x * 9;

}

int main()

{

    while (~scanf("%s", s))

    {

        memset(a, 0, sizeof(a));

        len = strlen(s);

        reverse(s, s + len);

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

            a[i] = (s[i] - '0') * 9;

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

        {

            a[i + 1] += a[i] / 10;

            a[i] %= 10;

        }

        if (a[len])

            len++;

        int l = 0, r = len * 2, ans = -1;

        while (l < r)

        {

            int mid = l + r >> 1;

            if (check(mid))

            {

                ans = mid;

                r = mid;

            }

            else

                l = mid + 1;

        }

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

    }

    return 0;

}


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

using namespace std;



#define ll long long

#define pb push_back



const int maxn = 1e5 + 20;



string s;



int mkay()

{

	int n = s.size();



	s[n - 1]++;

	for(int j = n - 1; j >= 0; j--)

	{

		if(s[j] <= '9')

			return j;



		s[j - 1]++;

		s[j] = '0';

	}

}



int main()

{

	ios_base::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);



	cin >> s;



	int n = s.size() , res = 0;

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

	{

		res++;

		int n = s.size();

		int last = i , j = i + 1;



		while(j < n && s[j] >= s[j - 1])

		{

			if(s[j] > s[j - 1])

				last = j;

			j++;

		}



		if(j == n)

			break;



		while(i < last + 1)

			s[i] = '0' , i++;

		i--;



		if(mkay() <= j)

			continue;



		i++;

		while(i < j)

		{

			s[i] = '0';

			res++;

			i++;



			if(mkay() <= j)

				break;

		}

		i--;



	}



	cout << res << endl;

}


















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

using namespace std;

char s[1000001];

char t;

int	ans;

int a[1000001];

bool check(int x)

{

	int n=strlen(s+1),kum=0;

	for(int i=1;i<=n;i++) a[i]=(s[i]-'0')*9;

	a[1]+=9*x;

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

	{

		if(a[i]>9)

		{

			if(i==n) a[++n]=0;

			a[i+1]+=a[i]/10;

			a[i]%=10;

		}

	}

	for(int i=1;i<=n;i++) kum+=a[i];

	return kum<=x*9;

}

int main()

{

	scanf("%s",s+1); 

	int l=1,r=strlen(s+1);

	reverse(s+1,s+r+1);

	while(l<=r)

	{

		int mid=(l+r)/2;

		if(check(mid)==1)

			ans=mid,r=mid-1;

		else

			l=mid+1;

	}

	cout << ans << endl;

	return 0;

} 

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

#include<cstring>

#include<algorithm>

using namespace std;

char num[555555];

int j,sum=0,a[555555];

int main()

{

	scanf("%s",num);

	int n=strlen(num);

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

	{

		a[i]=(num[n-i]-'0')*9;

	}

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

	{

		a[i+1]+=a[i]/10;a[i]%=10;

	}

	if(a[n+1])

	{

		n++;

	}

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

	{

		sum+=a[i];

	}

	for(int k=1;k<=n*10;k++)

	{

		a[1]+=9;

		sum+=9;

		j=1;

		while(j<=n)

		{

			if(a[j]<10)

			{

				break;

			}

			sum-=10;

			a[j]-=10;

			sum++;

			a[j+1]++;

			j++;

			if(j==n&&a[j+1])

			{

				n++;

			}

		}

		if(sum<=9*k)

		{

			printf("%d\n",k);

			return 0;

		}

	}

	return 0;

}

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

#include<cstdio>

#include<cstring>

using namespace std;

#define MAX 500500

char ch[MAX];

int a[MAX<<1],n,s;

int main()

{

	scanf("%s",ch+1);n=strlen(ch+1);

	for(int i=n;i;--i)a[i]=(ch[n-i+1]-48)*9;

	for(int i=1;i<=n;++i)a[i+1]+=a[i]/10,a[i]%=10;

	if(a[n+1])++n;

	for(int i=1;i<=n;++i)s+=a[i];

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

	{

		a[1]+=9;int p=1;s+=9;

		while(a[p]>=10)

		{

			s-=a[p+1];a[p+1]+=a[p]/10;s+=a[p+1];

			s-=a[p];a[p]%=10;s+=a[p];

			++p;if(p>n)n=p;

		}

		if(s<=i*9){printf("%d\n",i);return 0;}

	}

	return 0;

}


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

#include<cstring>

#include<algorithm>

using namespace std;

char num[555555];

int j,sum=0,a[555555];

int main()

{

	scanf("%s",num);

	int n=strlen(num);

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

	{

		a[i]=(num[n-i]-'0')*9;

	}

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

	{

		a[i+1]+=a[i]/10;a[i]%=10;

	}

	if(a[n+1])

	{

		n++;

	}

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

	{

		sum+=a[i];

	}

	for(int k=1;k<=n*10;k++)

	{

		a[1]+=9;

		sum+=9;

		j=1;

		while(j<=n)

		{

			if(a[j]<10)

			{

				break;

			}

			sum-=10;

			a[j]-=10;

			sum++;

			a[j+1]++;

			j++;

			if(j==n&&a[j+1])

			{

				n++;

			}

		}

		if(sum<=9*k)

		{

			printf("%d\n",k);

			return 0;

		}

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <sstream>

#include <iomanip>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cctype>

#include <cstring>

#include <vector>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <iterator>

#include <bitset>

#include <ctime>

#include<complex>

using namespace std;



#define FOR(i,a,b) for (int i = (a); i < (b); i++)

#define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)

#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)

#define FILL(a,value) memset(a, value, sizeof(a))



#define SZ(a) (int)a.size()

#define ALL(a) a.begin(), a.end()

#define PB push_back

#define MP make_pair



typedef long long LL;

typedef vector<int> VI;

typedef pair<int, int> PII;



const double PI = acos(-1.0);

const int INF = 1000 * 1000 * 1000 + 7;

const LL LINF = INF * (LL)INF;



const int MAX = 5 * 100000 + 47;

const int MOD = 1000 * 1000 * 1000 + 7;



int A[MAX];

string s;

int n;

int summ = 0;



void addOne()

{

	FOR(i, 0, n)

	{

		if (A[i] != 9)

		{

			summ++;

			A[i]++;

			break;

		}



		summ -= 9;

		A[i] = 0;

	}

}



int main()

{

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

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

	ios::sync_with_stdio(false); cin.tie(0);

	cin >> s;

	n = SZ(s);

	FOR(i, 0, n)

	{

		A[i] = s[n - i - 1] - '0';

	}



	int nex = 0;

	FOR(i, 0, n + 1)

	{

		int val = A[i] * 9 + nex;

		A[i] = val % 10;

		nex = val / 10;

	}



	if (A[n]) n++;

	FOR(i, 0, n)

	{

		summ += A[i];

	}



	FOR(k, 1, MAX)

	{

		FOR(i, 0, 9)

		{

			addOne();

		}



		if (summ <= 9 * k)

		{

			cout << k << endl;

			return 0;

		}

	}

}

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

#include<cstring>

#include<algorithm>

#define maxn 500005

using namespace std;

int n,x[maxn],sum;

char s[maxn];

int main()

{

	scanf("%s",s+1);

	n=strlen(s+1);

	reverse(s+1,s+n+1);

	for(int i=1;i<=n;i++) x[i]=(s[i]-'0')*9;

	for(int i=1;i<=n;i++) x[i+1]+=x[i]/10,x[i]%=10;

	if(x[n+1]) n++;

	for(int i=1;i<=n;i++) sum+=x[i];

	for(int k=1;k<=n*2;k++)

	{

		int v=9,j=1;

		while(v)

		{

			sum-=x[j],x[j]+=v;

			v=x[j]/10,x[j]%=10;

			sum+=x[j];

			if(j>n) n++;

			j++;

		}

		if(sum<=9*k) { printf("%d\n",k); return 0; }

	}

}

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



using namespace std;



#define For(i,a,b) for(ll i=a;i<b;i++)

#define Ford(i,a,b) for(ll i=a;i>=b;i--)

#define RET(x) { cout << x; exit(0); }

#define smin(a,b) a=min(a,b)

#define smax(a,b) a=max(a,b)

#define SZ(x) ((ll)((x).size()))

#define PB push_back

#define ER(x) cout << #x << ' ' << x << '\n';

#define X first

#define Y second



typedef long long int LL;

typedef LL ll;

typedef vector<ll> vll;

typedef pair<ll,ll> pll;

typedef string str;



const ll M=5e5+5,LG=30,mod=924844033;

ll pw(ll x,ll y){ if (y==0) return 1; return pw(x*x%mod,y/2)*(y&1?x:1)%mod; }



#define MOK(x) if (x>=mod) x-=mod;



struct bignum{

  ll ar[M];

  ll siz=0;

  void read(str s){

    while (SZ(s)){

      ar[siz]=s.back()-'0';

      s.pop_back();

      siz++;

    }

  }

  void mult9(){

    ll e=0;

    For(i,0,siz){

      ll p=ar[i]*9+e;

      e=p/10;

      ar[i]=p%10;

    }

    if (e){

      ar[siz++]=e;

    }

  }

  void plusplus(){

    for (ll i=0;1;i++){

      if (ar[i]!=9){

	ar[i]++;

	if (ar[siz]) siz++;

	return;

      }

      ar[i]=0;

    }

  }

  void decer(){

    ar[siz-1]--;

    while (siz && ar[siz-1]==0) siz--;

  }

  bool is0(){

    return (siz==0);

  }

  void chap(){

    For(i,0,siz) cout << ar[i];

    cout << '\n';

  }

};



bignum n;

  

int main(){

  ios::sync_with_stdio(0);

  str s;

  cin >> s;

  n.read(s);

  n.mult9();

  //n.chap();

  //return 0;

  ll tused=0;

  while (!n.is0()){

    n.plusplus();

    n.decer();

    tused++;

    //ER(tused);

    //n.chap();

    //if (tused>20) return 0;

  }

  RET((tused+8)/9);

}


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

#include<cstring>

#include<algorithm>

#define maxn 500005

using namespace std;

int n,x[maxn],sum;

char s[maxn];

int main()

{

	scanf("%s",s+1);

	n=strlen(s+1);

	reverse(s+1,s+n+1);

	for(int i=1;i<=n;i++) x[i]=(s[i]-'0')*9;

	for(int i=1;i<=n;i++) x[i+1]+=x[i]/10,x[i]%=10;

	if(x[n+1]) n++;

	for(int i=1;i<=n;i++) sum+=x[i];

	for(int k=1;k<=n*2;k++)

	{

		int v=9,j=1;

		while(v)

		{

			sum-=x[j],x[j]+=v;

			v=x[j]/10,x[j]%=10;

			sum+=x[j];

			if(j>n) n++;

			j++;

		}

		if(sum<=9*k) { printf("%d\n",k); return 0; }

	}

}

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

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#define SF scanf

#define PF printf

#define MAXN 110

#define MOD 1000000007

#define eisiorti sort

using namespace std;

int a[MAXN];

int n;

int dp[MAXN/2][MAXN][MAXN];

int main(){

	SF("%d",&n);

	for(int i=1;i<=2*n-1;i++)

		SF("%d",&a[i]);

	eisiorti(a+1,a+2*n);

	dp[n][1][0]=1;

	for(int i=n;i>=2;i--){

		int al=(a[i-1]!=a[i]);

		int ar=(a[2*n-i+1]!=a[2*n-i]);

		for(int l=0;l<=2*n-1;l++)

			for(int r=0;r+l<=2*n-1;r++)

				if(dp[i][l][r]){

					for(int dl=1;dl<=l+al;dl++)

						(dp[i-1][l+al-dl+1][r+ar+(dl>1)]+=dp[i][l][r])%=MOD;	

					for(int dr=1;dr<=r+ar;dr++)

						(dp[i-1][l+al+1][r+ar-dr]+=dp[i][l][r])%=MOD;	

				}

	}

	int ans=0;

	for(int l=0;l<=2*n-1;l++)

		for(int r=0;r+l<=2*n-1;r++)

			(ans+=dp[1][l][r])%=MOD;

	PF("%d",ans);

}

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

#include<algorithm>

using namespace std;

#define MAXN 55

#define MO 1000000007

void Add(int &x,int y)

{

	x=(x+y>=MO)?(x+y-MO):(x+y);

}

int dp[MAXN][MAXN*2][MAXN*2],n,a[MAXN*2],ans;

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n*2-1;i++)

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

	sort(a+1,a+n*2);

	dp[n][1][0]=1;

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

	{

		int al=(a[i]!=a[i+1]),ar=(a[n*2-i]!=a[n*2-i-1]);

		for(int l=0;l<=2*n-1;l++)

			for(int r=0;r+l<=2*n-1;r++)

				if(dp[i+1][l][r])

				{

					int t=dp[i+1][l][r];

					for(int dl=0;dl<l+al;dl++)

						Add(dp[i][l+al-dl][r+ar+(dl>0)],t);

					for(int dr=1;dr<=r+ar;dr++)

						Add(dp[i][l+al+1][r+ar-dr],t);

				}

	}

	for(int l=0;l<=2*n-1;l++)

		for(int r=0;r+l<=2*n-1;r++)

			Add(ans,dp[1][l][r]);

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

}

// Fastest known solution for this problem:
// Original C++ solution (slower):


// dpの練習

// dpでなく、愚直に組んだプログラミング

// ナップサック問題とほぼ同じ



#include <iostream>

#include <algorithm>

#include <cstring>



using namespace std;



int wei; // 持てる最大の重さ

int n; // お宝の数

int v[1001]; // お宝の価値

int w[1001]; // お宝の重さ

 // グローバル配列は0で初期化されている

int dp[1001][1001]; //メモテーブル



int max_value(int i, int j) {

  int value;



  if( dp[i][j] >= 0 ){

    return dp[i][j];

    //すでに１回は調べている

  }

 

  if (i == n) {

    // 品物がもう残っていないときは、価値の和の最大値は0で確定

    //もうお宝がないつまり、価値は0

    value = 0;

  } else if (j < w[i]) {

    //風呂敷が持てる重さを超えてしまう

    // 残りの容量が足りず品物iを入れられないので、入れないパターンだけ処理

    // i+1 以降の品物のみを使ったときの最大値をそのままこの場合の最大値にする

    value = max_value(i + 1, j);

  } else {

    //左がお宝を入れない、右がお宝を入れた場合

    // 品物iを入れるか入れないか選べるので、両方試して価値の和が大きい方を選ぶ

    value = max( max_value(i + 1, j), max_value(i + 1, j - w[i]) + v[i] );

  } 

  return dp[i][j] = value;

  //メモに記憶させる

}



void max_weight( int ans ){



  int w_min;

   

  for (int i = wei -1 ; i >= 0 ; i--){

    if( ans != max_value( 0 , i ) ){

         w_min = i + 1;

         break;

    }

  }

  cout << w_min << endl;  

}





int main(void){



  int cnt = 1;

  while( cin >> wei ){

    memset( dp , -1 , sizeof(dp) );

    //まだ調べてないところを-1で初期化

    if( wei == 0 )break;

    cin >> n;

    char ten;

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

      cin >> v[i] >> ten >> w[i];

    }

    cout << "Case " << cnt << ":" << endl;

    int ans = max_value( 0 , wei );

    cout << ans << endl;

    max_weight(ans);

    cnt++;

  }

  return 0;

}

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

#include <cstring>

#include <algorithm>

#define MAX 1000

using namespace std;



int main(void){



  int n,W;

  int w[MAX+1];

  int v[MAX+1];

  int dp[MAX+1][MAX+1];

  char ten;

  int cnt = 1;



  while( cin >> W , W ){

    cin >> n;

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

      cin >> v[i] >> ten >> w[i];

    }



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

      for( int j = 0 ; j < MAX ; j++ ){

	dp[i][j] = 0;

      }

    }



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

      for( int j = 0 ; j <= W ; j++ ){

	if(j < w[i] ) dp[i+1][j] = dp[i][j];

	else dp[i+1][j] = max( dp[i][j] , dp[i][j-w[i]] + v[i] );

      }

    }

    

    cout << "Case " << cnt++ << ":" << endl;

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

      if( dp[n][i] != dp[n][W] ){

	cout << dp[n][W] << endl << i+1 << endl;

	break;

      }

    }

  }  

  return 0;

}

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

#include <algorithm>

#include <cstring>



using namespace std;



int wei; // 持てる最大の重さ

int n; // お宝の数

int v[1001]; // お宝の価値

int w[1001]; // お宝の重さ

 // グローバル配列は0で初期化されている

int dp[1001][1001]; //メモテーブル



int max_value(int i, int j) {

  int value;



  if( dp[i][j] >= 0 ){

    return dp[i][j];

    //すでに１回は調べている

  }

 

  if (i == n) {

    // 品物がもう残っていないときは、価値の和の最大値は0で確定

    //もうお宝がないつまり、価値は0

    value = 0;

  } else if (j < w[i]) {

    //風呂敷が持てる重さを超えてしまう

    // 残りの容量が足りず品物iを入れられないので、入れないパターンだけ処理

    // i+1 以降の品物のみを使ったときの最大値をそのままこの場合の最大値にする

    value = max_value(i + 1, j);

  } else {

    //左がお宝を入れない、右がお宝を入れた場合

    // 品物iを入れるか入れないか選べるので、両方試して価値の和が大きい方を選ぶ

    value = max( max_value(i + 1, j), max_value(i + 1, j - w[i]) + v[i] );

  } 

  return dp[i][j] = value;

  //メモに記憶させる

}



void max_weight( int ans ){



  int w_min;

   

  for (int i = wei -1 ; i >= 0 ; i--){

    if( ans != max_value( 0 , i ) ){

         w_min = i + 1;

         break;

    }

  }

  cout << w_min << endl;  

}





int main(void){



  int cnt = 1;

  while( cin >> wei ){

    memset( dp , -1 , sizeof(dp) );

    //まだ調べてないところを-1で初期化

    if( wei == 0 )break;

    cin >> n;

    char ten;

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

      cin >> v[i] >> ten >> w[i];

    }

    cout << "Case " << cnt << ":" << endl;

    int ans = max_value( 0 , wei );

    cout << ans << endl;

    max_weight(ans);

    cnt++;

  }

  return 0;

}

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

#include <cstring>

#include <algorithm>

#define MAX 1000

using namespace std;



int main(void){



  int n,W;

  int w[MAX+1];

  int v[MAX+1];

  int dp[MAX+1][MAX+1];

  char ten;

  int cnt = 1;



  while( cin >> W , W ){

    cin >> n;

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

      cin >> v[i] >> ten >> w[i];

    }



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

      for( int j = 0 ; j < MAX ; j++ ){

	dp[i][j] = 0;

      }

    }



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

      for( int j = 0 ; j <= W ; j++ ){

	if( j < w[i] ) dp[i+1][j] = dp[i][j];

	else dp[i+1][j] = max( dp[i][j] , dp[i][j-w[i]] + v[i] );

      }

    }

    

    cout << "Case " << cnt++ << ":" << endl;

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

      if( dp[n][i] != dp[n][W] ){

	cout << dp[n][W] << endl << i+1 << endl;

	break;

      }

    }

  }  

  return 0;

}

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

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <map>

#include <set>

#include <queue>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <sstream>

#include <vector>

#include <string>

#include <iomanip>

#include <bitset>

#define INF	100000000

#define pb	push_back

#define fi first

#define sec second

#define SS stringstream

using namespace std;

typedef pair<int, int> P;

typedef long long int	ll;



int w, n;

int t = 0;

int dp[1001][1001];

vector<P> vec;



int rec(int i, int j){

	if(dp[i][j] >= 0) return dp[i][j];

	int res;

	if(i == n) res = 0;

	else if(j < vec[i].sec) res = rec(i+1, j);

	else res = max(rec(i+1, j), rec(i+1, j-vec[i].sec)+vec[i].fi);

	return dp[i][j] = res;

}



int main(){

	while(scanf("%d", &w)){

		t++;

		if(w == 0) break;

		memset(dp, -1, sizeof(dp));

		scanf("%d", &n);

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

			int temp1, temp2;

			char trash;

			scanf("%d%c%d", &temp1, &trash, &temp2);

			vec.pb(P(temp1, temp2));

		}

		printf("Case %d:\n", t);

		printf("%d\n", rec(0, w));

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

			if(rec(0, w-i) != rec(0,w)){

				printf("%d\n", w-i+1);

				break;

			}

		}

		vec.clear();

	}

}

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

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

using namespace std;

typedef long long ll;

typedef pair<ll,ll> P;

 

const double EPS = 1e-10;

const ll INF = 100000000;

const ll MOD = 1000000007;



struct ITEM {

    int v, w;

    double x;



    bool operator>(const ITEM& right) const {

        return x > right.x;

    }

} item[1000];



int N, W;

int v[1000], w[1000];

int ans;

int ans2;



void dfs (int pos, int val, int sum, bool flag) {

    if (ans < val) {

        ans = val;

        ans2 = sum;

    }

    if (ans == val) {

        ans2 = min(ans2, sum);

    }

    if (pos == N) return;

    if (flag) {

        int _W = W-sum;

        double lim = val;

        for (int i = pos; i < N; i++) {

            if (_W >= item[i].w) {

                lim += item[i].v;

                _W -= item[i].w;

            } else {

                lim += _W * item[i].x;

                break;

            }

        }

        if (lim+EPS < ans) {

            return;

        }

    }

    if (sum+item[pos].w <= W) {

        dfs(pos+1, val+item[pos].v, sum+item[pos].w, false);

    }

    dfs(pos+1, val, sum, true);

}



int main() {

    int testcase = 1;

    while (cin >> W) {

        if (W == 0) break;

        ans = 0;

        cin >> N;

        rep(i,N) {

            char tmp;

            cin >> item[i].v >> tmp >> item[i].w;

            item[i].x = item[i].v / (double)item[i].w;

        }

        sort(item, item+N, greater<ITEM>());

        dfs(0, 0, 0, false);

        cout << "Case " << testcase << ":" << endl;

        cout << ans << endl;

        cout << ans2 << endl;

        testcase++;

    }

}






// Fastest known solution for this problem: