Go: package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
)

const MaxW = 1000
const MaxN = 1000

type Tuple struct {
	Value  int
	Weight int
}

func nextLine(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

func solve(w int, n int, vws []Tuple) Tuple {
	var dp [MaxN + 1][MaxW + 1]int

	for i := 0; i < n; i++ {
		for j:= w; j > 0; j-- {
			if j < vws[i].Weight {
				dp[i + 1][j] = dp[i][j]
			} else {
				dp[i + 1][j] = int(math.Max(float64(dp[i][j]), float64(dp[i][j - vws[i].Weight] + vws[i].Value)))
			}
		}
	}

	maxValue := dp[n][w]
	minWeight := w

	for j := w - 1; j > 0; j-- {
		if maxValue == dp[n][j] {
			minWeight = j
		} else {
			break
		}
	}

	return Tuple{Value: maxValue, Weight: minWeight}
}

func main() {
	var sc = bufio.NewScanner(os.Stdin)
	index := 1
	for {
		var w, n int
		w, _ = strconv.Atoi(nextLine(sc))
		if w == 0 {
			return
		}
		n, _ = strconv.Atoi(nextLine(sc))

		vws := make([]Tuple, n, n)
		for i := 0; i < n; i++ {
			array := strings.Split(nextLine(sc), ",")
			v, _ := strconv.Atoi(array[0])
			w, _ := strconv.Atoi(array[1])
			vws[i] = Tuple{Value: v, Weight: w}
		}

		t := solve(w, n, vws)
		fmt.Printf("Case %d:\n", index)
		fmt.Println(t.Value)
		fmt.Println(t.Weight)
		index++
	}
}

C++: #include "bits/stdc++.h"

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back

int dp[2000][2000];



int main(){
	int W;
	int n;
	int c=0;
	while(cin>>W){
		c++;
		if(W==0)break;
		char ch;
		int w[2000],v[2000];
		rep(i,2000)rep(j,2000)dp[i][j]=-999999999;
		cin>>n;
		rep(i,n){
			cin>>v[i]>>ch>>w[i];
		}

		int maxval=-1;
		int maxwait=-1;

		dp[0][0]=0;
		for(int i=1;i<n;i++){
			rep(j,W){
				dp[i][j] = max(dp[i][j],dp[i-1][j]);
				if(j-w[i]>=0)
					dp[i][j] = max(dp[i][j],dp[i-1][j-w[i]]+v[i] );

				if(maxval<dp[i][j]){
					maxval=dp[i][j];
					maxwait=j;
				}
				if(maxval==dp[i][j] && maxwait>j){
					maxval=dp[i][j];
					maxwait=j;
				}
			}
		}
		cout<<"Case "<<c<<":"<<endl;
		cout<<maxval<<endl;
		cout<<maxwait<<endl;
	}
}

C++: #include<stdio.h>
#include<string>
#include<stdlib.h>
#include<math.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
#include<string.h>
#include<map>
#include<queue>

using namespace std;

typedef pair<int,int> pii;

#define rep(i,j) for(int i=0;i<(j);i++)
#define reps(i,j,k) for(int i=j;i<=k;i++)
#define in(i,j,k) ((i)>=(j)&&(i)<=(k))

int dp[1001][1000];

int main(){
	int n,W,v[1000],w[1000],c=0,ans,we;
	for(;;){
		scanf("%d",&W);
		if(!W)break;
		scanf("%d",&n);
		ans=0;
		we=1023;
		rep(i,n)scanf("%d,%d",v+i,w+i);
		rep(i,n)rep(j,W)dp[j][i]=0;
		reps(i,1,W){
			reps(j,1,n-1){
				if(w[j]<=i)dp[i][j]=max(dp[i-1][j-1],dp[i-w[j]][j-1]+v[j]);
				else dp[i][j]=dp[i][j-1];
				ans=max(ans,dp[i][j]);
			}
		}
		for(int i=0;i<=W&&we==1023;i++)rep(j,n)if(dp[i][j]==ans){we=i;break;}
		printf("Case %d:\n%d\n%d\n",++c,ans,we);
	}
	return 0;
}

C++: #include<iostream>

using namespace std;

class item
{
public:
	int value;
	int weight;
	bool flag;
};

bool input(int *c, int *n, item it[1000])
{
	cin>>*c;
	if(*c==0)
	{
		return false;
	}
	cin>>*n;
	for(int i=0;i<*n;i++)
	{
		char t;
		cin>>it[i].value>>t>>it[i].weight;
	}
	return true;
}

item max(item a, item b)
{
	if(a.value>b.value)
	{
		return a;
	}
	else
	{
		return b;
	}
}

item add(item a, item b)
{
	a.value+=b.value;
	a.weight+=b.weight;
	return a;
}

item table[1000][1000];

item solve(int c, int n, item it[1000])
{
	if(table[c][n].flag!=true){
		if(c==0||n==0)
		{
			table[c][n].value=0;
			table[c][n].weight=0;
		}
		else if(c<it[n-1].weight)
		{
			table[c][n]=solve(c,n-1,it);
		}
		else
		{
			table[c][n]=max(solve(c,n-1,it),add(solve(c-it[n-1].weight,n-1,it),it[n-1]));
		}
		table[c][n].flag=true;
	}
	return table[c][n];
}

int main(void)
{
	for(int i=1;;i++)
	{	
		int c,n;
		item it[1000];
		if(input(&c,&n,it)==false)
		{
			break;
		}
		for(int k=0;k<1000;k++)
		{
			for(int j=0;j<1000;j++)
			{
				table[i][j].flag=false;
				table[i][j].value=0;
				table[i][j].weight=0;
			}
		}
		item ans=solve(c,n,it);
		cout<<"Case "<<i<<':'<<endl<<ans.value<<endl<<ans.weight<<endl;
	}
	return 0;
}

C++: #include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
 
using namespace std;
 
#define pb(n)	push_back(n)
#define mp(n,m) make_pair(n,m)
#define fi 	first
#define se 	second
#define all(r) r.begin(),r.end()

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const int IMAX=((1<<30)-1)*2+1;
const double EPS=1e-9;
//int mod=1000000007;

vector<pii> v(1010,pii(0,0));
vector<vi> dp(1010,vi(1010,-1));
int N,W;

int ap=0,aw=0;

void init(){
	for(int i=0; i<N+1; i++){
		for(int j=0; j<W+1; j++){
			dp[i][j]=-1;
		}
		v[i]=mp(0,0);
	}
	ap=0;
	aw=0;
}

int calc(int n,int w){
	if(dp[n][w]!=-1)return dp[n][w];
	int ret;
	int t=w;
	if(n==N)ret=0;
	else if(w+v[n].second>W)ret=calc(n+1,w);
	//else ret=max(calc(n+1,w),calc(n+1,w+v[n].second)+v[n].first);
	else{
		int a=calc(n+1,w),b=calc(n+1,w+v[n].second)+v[n].first;
		if(b>a)t+=v[n].second;
		ret=max(a,b);
		//if(a==0&&b==10)cout<<n<<" "<<ret<<" "<<t<<endl;
	}
	// if(ret>=ap){
	// 	ap=ret;
	// 	aw=w;
	// 	cout<<ap<<" "<<aw<<endl;
	// }
	if(ret>ap){
		ap=ret;
		aw=t;
	}
	//cout<<ret<<" "<<n<<" "<<t<<endl;
	return dp[n][w]=ret;
}



int main(){
	int k=0;
	char c;
	while(++k){
		cin>>W;
		//cout<<"    W        "<<W<<endl;
		if(W==0)break;
		cin>>N;
		init();
		for(int i=0; i<N; i++){
			cin>>v[i].first>>c>>v[i].second;
		}
		calc(0,0);
		cout<<"Case "<<k<<":"<<endl;
		cout<<ap<<endl;
		cout<<aw<<endl;
		//scout<<v[4].first<<endl;;
		// for(int i=0; i<N+1; i++){
		// 	for(int j=0; j<W+1; j++){
		// 		if(dp[i][j]==220)cout<<i<<" "<<j<<endl;
		// 	}
		// }
	}
}

C++: #include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<complex>
#include<map>

#define f first
#define s second

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()
#define EPS (1e-10)
using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef complex<double> P;

int memo[1010];
int w,n;
int wei[1000];
int val[1000];

void search(int p){
  if(p == n) return;
  int ww = wei[p];
  int vv = val[p];
  for(int i=w-ww; i>=0; i--) if(memo[i] != -1) {
      memo[ww+i] = max(memo[ww+i], memo[i] + vv); 
  }
  search(p+1);
}

int main(){
  int cc = 1;
  while(scanf("%d",&w),w){
    scanf("%d",&n);
    REP(i,n) scanf("%d,%d",val+i,wei+i);
    memset(memo,-1,sizeof(memo));
    memo[0] = 0;
    search(0);
    int vv = 0, ww = 0;
    REP(i,w+1){
      if(memo[i] > vv){
	vv = memo[i];
	ww = i;
      }
    }
    printf("Case %d:\n",cc++);
    printf("%d\n",vv);
    printf("%d\n",ww);
  }
  return 0;
}