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++: #define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;

//#define int long long
#define DBG 1
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define each(it,c) for(auto it=(c).begin();it!=(c).end();it++)
#define all(c) c.begin(),c.end()
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);
class takara {
public:
	int v, w;
	takara() {}
	takara(int x, int y) :v(x), w(y) {}
	bool operator<(const takara &other) {
		return this->w < other.w;
	}
};
signed main() {
	int W; int x(1);
	while (cin >> W, W) {
		int N; cin >> N;
		vector<takara>list;
		list.push_back(takara(0, 0));
		rep(i, 0, N) {
			int w, v; char c; cin >> v >> c >> w;
			list.push_back(takara(v, w));
		}
		vector<vector<int > >v(N + 1, vector<int>(W + 1, 0));
		rep(i, 1, N + 1) {
			rep(j, 1, W + 1) {
				v[i][j] = v[i - 1][j];
				if (j - list[i].w >= 0) {
					v[i][j] = max(v[i - 1][j], v[i - 1][j - list[i].w] + list[i].v);
				}
			}
		}
		int ret(0);
		rep(i, 0, W + 1) {
			if (v[N][ret] < v[N][i])ret = i;
		}
		cout << "Case " << x++ << ":" << endl;
		cout << v[N][W-1] << endl << ret << endl;
	}
	return 0;
}

C++: #include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,x,n) for(int i=x;i<n;i++)
#define pb push_back
#define MAX 100005
#define int long long
using namespace std;
const int MOD=1000000007;
const int INF=1000000009;



signed main(){
  int W,N;
  int c=1;
  while(cin>>W>>N,W){
    vector<int> v(N),w(N);
    char x;
    vector<vector<int> > dp(N+1,vector<int>(W+1));
    rep(i,N)cin>>v[i]>>x>>w[i];
    loop(i,1,N+1){
      rep(j,W+1){
        if(j-w[i-1]>=0){
          dp[i][j]=max(dp[i-1][j-w[i-1]]+v[i-1],dp[i][j]);
        }else{
          dp[i][j]=dp[i-1][j];
        }
      }
    }
    int val=dp[N][W],wei;
    rep(i,W+1){
      if(dp[N][i]==val)wei=i;
    }
    cout<<"Case "<<c<<':'<<endl;
    cout<<val<<endl;
    cout<<wei<<endl;
    c++;
  }

  return 0;
}

C++: #include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define latte WORLD

int N,W,tv[1000],tw[1000];
int memo[1000][1001],ansv,answ;

int latte(int n,int v,int w){
    if(w>W) return 0;
    if(n==N){
        if(ansv<v || (ansv==v && answ>w)){
            ansv = v; answ = w;
        }
        return v;
    }
    if(memo[n][w]!=-1) return memo[n][w];
    int ans=0;
    memo[n][w] = max(latte(n+1,v+tv[n],w+tw[n]),latte(n+1,v,w));
    return memo[n][w];
}

int main(){
    for(int ds=1;cin>>W,W;ds++){
        cin>>N;
        for(int i=0;i<N;i++) scanf("%d,%d",&tv[i],&tw[i]);
        for(int i=0;i<1000;i++)for(int j=0;j<1001;j++) memo[i][j] = -1;
        ansv = 0;
        latte(0,0,0);
        printf("Case %d:\n%d\n%d\n",ds,ansv,answ);
    }
}

C++: #include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int mp[1001][1001];

int main(){
	int W;char c;
	for(int num = 0;cin >> W&&W;num++){
		int v[1001], w[1001], n;
		cin >> n;
		fill((int*)mp, (int*)(mp+n+1), 0);
		for(int i = 0;i < n;i++)cin >> v[i] >> c >> w[i];
		for(int i = 0;i < n;i++){
			
			for(int j = 0;j < W+1;j++){
				if(j < w[i])mp[i+1][j] = mp[i][j];
				else mp[i+1][j] = max(mp[i][j], mp[i][j-w[i]]+v[i]);
			}
		}
		
		int ans = 0;
		for(int i = 1;i < W+1;i++){
			if(mp[n][i] > mp[n][ans])ans = i;
		}
		cout << "Case " << num+1 << ":" << endl;
		cout << mp[n][ans] << endl << ans << endl;
	}
	return 0;
}
/*
1
y eazqyp pnop pngtg ye obmpngt xmybp mr lygw
*/

C++: #include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;

#define all(c) (c).begin(), (c).end()
#define pb push_back
#define mp make_pair
#define EXIST(v,i) (find(all(v), i) != (v).end())
#define ERASE(v,i) (v).erase(remove(all(v), i), (v).end())
#define INDEX(v,i) (find(all(v), i) - (v).begin())
#define rep(i,n) for(int i = 0; i < (int)n; ++i)
#define debug(x) cerr << #x << " = " << (x) << endl;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

const int INF = 100000000;
const double PI = 3.14159265358979323846;
const double EPS = 1e-10;

int main() {
	int CaseSet = 1;
	for(int W; scanf("%d", &W), W;) {
		int N; scanf("%d", &N);
		vector<int> value(N);
		vector<int> weight(N);
		rep(i,N) scanf("%d,%d", &value[i], &weight[i]);

		int dp[N][W+1];
		memset(dp, 0, sizeof dp);
		for(int j = weight[0]; j <= W; j++) dp[0][j] = value[0];
		for(int i = 1; i < N; i++) {
			for(int j = weight[i]; j <= W; j++) {
				int t = dp[i - 1][j - weight[i]] + value[i];
				dp[i][j] = max(dp[i][j], t);
			}
		}

		int vans = dp[N-1][W];
		int ind = find(dp[N - 1], dp[N - 1] + W, vans) - dp[N - 1];

		cout << "Case " << CaseSet++ << ":" <<endl;
		cout << vans << endl;
		cout << ind << endl;
	}
	return 0;
}

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

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

using namespace std;

int main(){
	int c = 1;
	int w;
	while(cin >> w && w){
		int n;
		int tr[1024][2];
		// 価値を最大に
		// 入れた数 重さ合計 価値
		int dp[1024][1024];
		
		cin >> n;
		rep(i, n){
			scanf("%d, %d", &tr[i][0], &tr[i][1]);
		}

		rep(i, n){
			dp[1][tr[i][1]] = tr[i][0];
		}
		
		rep(i, n){
			for(int j = 0; j <= w; j++){
				if(dp[i][j] != 0){
					int value = dp[i][j] + tr[i][0];
					int we = j + tr[i][1];
					if(we <= w){	
						dp[i + 1][we] = max(dp[i+1][we], value);
					} else {
						dp[i + 1][j] = max(dp[i+1][j], dp[i][j]);
					}
				}
			}
		}
		
		int mv,mw;
		mv = 0; mw = 0;
		rep(i, n){
			for(int j = 0; j <= w; j++){
				if(dp[i][j] > mv){
					mv = dp[i][j];
					mw = j;
				}
			}
		}

		cout << "Case " << c << ':' << endl;
		cout << mv << endl;
		cout << mw << endl;

		c++;
	}
	return 0;
}