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 <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
using namespace std;
 
#define rep(i,n) for(int i=0; i<n; i++)
#define repa(i,s,e) for(int i=s; i<=e; i++)
 
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

int W,N;
const int MAX_N = 1001;
const int MAX_W = 1001;
int v[MAX_N];
int w[MAX_N];
int dp[MAX_N][MAX_W];

void solve() {
	memset(dp, 0, sizeof(dp));
	repa(i,1,N) {
		repa(j,0,W) {
			if(j + w[i] < W) {
				rep(k,i) {
					dp[i][j + w[i]] = max(dp[i][j + w[i]], dp[k][j] + v[i]);
				}
			}
		}
	}

	int maxval = -1;
	int weight = 0;
	repa(i,0,W) {
		if(maxval < dp[N][i]) {
			maxval = dp[N][i];
			weight = i;
		}
	}
	cout <<	maxval << endl;
	cout << weight << endl;
}

int main() {
	int c = 0;
	while(cin>>W, W) {
		cin >> N;
		rep(i,N) {
			scanf("%d,%d", &v[i], &w[i]);
		}

		printf("Case %d:\n", ++c);
		solve();
	}
}

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


using namespace std;


int W, N;
int w[1001];
int v[1001];
int dp[1001][1001];

int main()
{
	for (int caseCount = 1; ; ++caseCount)
	{
		scanf("%d", &W);
		if (W == 0)
			break;
		scanf("%d", &N);
		for (int i = 0; i < N; ++i)
		{
			int a, b;
			scanf("%d,%d", &a, &b);
			v[i] = a;
			w[i] = b;
		}
		memset(dp, 0, sizeof(dp));

		for (int i = 0; i < N; ++i)
		{
			for (int j = 0; j <= W; ++j)
				dp[i+1][j] = max(dp[i][j], (w[i] <= j ? dp[i][j-w[i]]+v[i] : 0));
		}

		int mw, mv;
		mw = 9999;
		mv = -1;
		for (int i = 0; i <= W; ++i)
		{
			if (dp[N][i] > mv)
			{
				mv = dp[N][i];
				mw = i;
			}
		}
		printf("Case %d:\n%d\n%d\n", caseCount, mv, mw);
	}


	return 0;
}

C++: #define _USE_MATH_DEFINES
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<bitset>
#include<cctype>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<deque>
#include<list>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<queue>
#include<vector>
using namespace std;

int main() {
	int W, N;

	for (int h = 1; cin >> W&& W; h++) {
		cin >> N;
		int v, w;
		int dp[1001] = {};
		for (int i = 0; i < N; i++) {
			char c;
			cin >> v >> c >> w;
			for (int j = W; j > 0; j--) {
				if (j - w < 0)continue;
				dp[j] = max(dp[j], dp[j - w] + v);
			}
		}
		int a = 0, b = 0;
		for (int i = 0; i < W; i++) {
			if (a < dp[i]) {
				a = dp[i];
				b = i;
			}
		}
		cout << "Case " << h << ":" << endl;
		cout << a << endl;
		cout << b << endl;
	}
	return 0;
}

C++: #include <cstdio>
#include <algorithm>
using namespace std;

int cnt, W, N, w[1000], v[1000], dp[1000][1001];

void solve(){
    for(int i = 0; i < N; i++){
        dp[i+1][w[i]] = v[i];
        for(int j = w[i]+1; j <= W; j++){
            dp[i+1][j] = 0;
            if( dp[i][j-w[i]] ){
                dp[i+1][j] = dp[i][j-w[i]] + v[i];
            }
        }
    }
    int c,v = 0;
    for(int i = 0; i < W; i++){
        if( dp[N][i] > v ){
            v = dp[N][i];
            c = i;
        }
    }
    printf("Case %d:\n%d\n%d\n", cnt, v, c);
}

int main(){
    cnt = 0;
    while( true ){
        cnt++;
        scanf("%d", &W);
        if( !W ) break;
        scanf("%d", &N);
        for(int i = 0; i < N; i++){
            scanf("%d,%d", v+i, w+i);
        }
        solve();
    }
    return 0;
}

C++: #include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <cmath>
#include <complex>
#include <map>
using namespace std;

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

static const double PI=6*asin(0.5);
typedef complex<double> P;
typedef long long ll;


int m;
int w,n;
pair <int,int> dp[1050][1050];
char t;
vector<pair <int,int> > pa;
pair<int,int> tpa;

pair<int,int> maxpair(pair <int,int> a,pair <int,int> b){
	return a.second==b.second ? a.first>b.first ? b:a  :  a.second>b.second ? a:b;
}

pair <int,int> rec(int i,int j){
	if(dp[i][j].second>=0) return dp[i][j];
	if(i==pa.size()){
		tpa.second = 0;
		tpa.first=0;
	}
	else if(j<pa[i].first){
		tpa = rec(i+1,j);
		
	}
	else{
		pair <int,int> tpa1=rec(i+1,j);
		pair <int,int> tpa2=rec(i+1,j-pa[i].first);
		tpa2.first+=pa[i].first;
		tpa2.second+=pa[i].second;
		tpa = maxpair(tpa1,tpa2);
	}
	return dp[i][j] = tpa;
	
}

int main(){
	int e=1;
	while(cin>>w,w!=0){
		memset(dp,-1,sizeof(dp));
		cout<<"Case "<<e++<<":\n";
		tpa.first=0;
		tpa.second=0;
		cin>>n;
		rep(i,n){
			int t1,t2;
			cin>>t1>>t>>t2;
			pair <int,int> tm;
			tm.first=t2;
			tm.second=t1;
			pa.push_back(tm);
		}
		//rep(i,pa.size())cout<<pa[i].first<<" "<<pa[i].second<<endl;
		rec(0,w);
		
		cout<<dp[0][w].second<<endl<<dp[0][w].first<<endl;
		pa.clear();
	}
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <utility>
#include <cstdio>
#include <algorithm>

using namespace std;

#define price first
#define weight second

int main(){
	int W;
	int cnt = 1;
	while (cin >> W, W) {
		int N; cin >> N;
		vector<pair<int, int> > tres(N);
		vector<int> dp(W+1);
		for (int i = 0; i < N; i++) { scanf("%d,%d", &tres[i].price, &tres[i].weight);}
		for (int i = 0; i < W+1; i++) { dp[i] = -1; }
		dp[0] = 0;

		sort(tres.begin(), tres.end());

		for (int i = 0; i < N; i++) {
			for (int j = W; j >= 0; j--) {
				if (dp[j] == -1) { continue; }
				if (j+tres[i].weight <= W) {
					if (dp[j+tres[i].weight] < dp[j]+tres[i].price) {
						dp[j+tres[i].weight] = dp[j]+tres[i].price;
					}
				}
			}
		}
		int PRICE = 0;
		int WEIGHT = 0;
		for (int i = W; i >= 0; i--) {
			if (PRICE <= dp[i]) {
				PRICE = max(PRICE, dp[i]);
				WEIGHT = i;
			}
		}

		cout << "Case " << cnt << ":" << endl;
		cout << PRICE << endl;
		cout << WEIGHT << endl;
		cnt++;
	}

	return 0;
}