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 <cmath>
#include <algorithm>
#include <vector>
#include <iterator>
#include <cstdio>
#include <numeric>
using namespace std;
int main(){
  for(int tc = 1;; ++tc){
    int W;
    cin >> W;
    if(W == 0){
      break;
    }
    int n;
    cin >> n;
    int value[n], weight[n];
    for(int i = 0; i < n; ++i){
      scanf("%d,%d", &value[i], &weight[i]);
    }
    int table[n+1][W+1];    
    fill_n((int*)table, (n+1)*(W+1), 0);
    table[0][0] = 0; 
    for(int i = 0; i < n; ++i){
      for(int w = 0; w <= W; ++w){
	if(table[i][w] != -1){
	  table[i+1][w] = table[i][w];
	}
      }
      for(int w = weight[i]; w <= W; ++w){
	int tmp = w - weight[i];
	if(table[i][tmp] >= 0){
	  table[i+1][w] = max(table[i+1][w], table[i][tmp] + value[i]);
	}
      }    
    }
    int ans_w = 0, ans_v = 0;
    for(int w = 0; w <= W; ++w){
      if(ans_v < table[n][w]){
	ans_v = table[n][w];
	ans_w = w;
      }
    }
    cout << "Case " << tc << ":" << endl;
    cout << ans_v << endl;
    cout << ans_w << endl;
  }
  return 0;
}

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

int main(){
	int W;char c;
	for(int num = 0;cin >> W&&W;num++){
		int v[1000], w[1000], 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 <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <algorithm>
#include <functional>

using namespace std;

#define rep(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define foreach(itr,c) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define MAX 1010

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

int main(){
  int i,j;

  for(;;){
    scanf("%d",&W); if(W == 0) break;
    scanf("%d",&N);
    rep(i,N) scanf("%d,%d",&v[i],&w[i]);

    rep(i,MAX) rep(j,MAX) dp[i][j] = 0;

    int res;
    for(i = 0; i <= N; i++){
      for(j = 0; j <= W; j++){
        if(j - w[i] < 0) dp[i+1][j] = dp[i][j];
        else {
          if(dp[i][j] < dp[i][j-w[i]] + v[i]){
            dp[i+1][j] = dp[i][j-w[i]] + v[i];
            res = j;
          }
          else dp[i+1][j] = dp[i][j];
        }
      }
    }

    printf("%d\n%d\n",dp[N][W],res);
  }

  return 0;
}

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

#define MAX 1000

int dp[MAX + 1][MAX + 1];
int v[MAX], w[MAX];

int main() {
	int W, n, u = 0;
	char t;
	while (cin >> W) {
		if (W == 0) break;
		cin >> n;
		u++;

		dp[MAX + 1][MAX + 1] = { 0 };
		for (int i = 0; i < n; i++) {
			cin >> v[i] >> t >> w[i];
		}

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

		int mv = 0, mw;
		for (int i = 0; i <= W; i++) {
			if (dp[n][i] > mv) {
				mv = dp[n][i];
				mw = i;
			}
		}

		cout << "Case " << u << ":" << endl;
		cout << mv << endl;
		cout << mw << endl;
	}
	return 0;
}

C++: #include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define o(a) cout << a << endl
#define int long long
// #define first first
// #define second se
using namespace std;
typedef pair<int, int> P;
typedef vector<int> vi;

int dp[1100][1100];

signed main(){
    int W;
    int cnt = 0;
    while(cin >> W, W){
        int n;
        cin >> n;
        cnt++;
        vector<int> v(n), w(n);
        rep(i, 0, n){
            char c;
            cin >> v[i] >> c >> w[i];
        }
        rep(i, 0, n + 1){
            rep(j, 0, W + 1){
                dp[i][j] = 0;
            }
        }
        dp[0][0] = 0;
        rep(i, 0, n){
            rep(j, 0, W + 1){
                if(j - w[i] >= 0){
                    dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
                }
            }
        }
        int ans = -1, wt = 0;
        rep(i, 0, W + 1){
            if(dp[n][i] > ans){
                ans = dp[n][i];
                wt = i;
            }
        }
        cout << "Case " << cnt << ":" << endl;
        o(ans);
        o(wt);
    }
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <ctype.h>

#define rep(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define all(v) (v).begin(), (v).end()
#define rev(s) (s).rbegin(), (s).rend()
#define MP make_pair
#define X first
#define Y second

using namespace std;

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

const int INF = 1000000000;
const double EPS = 1e-10;

int main(){
	int casenum = 0;
	while(1){
		int w, n;
		cin >> w >> n;
		if(!w) break;

		n++;
		vector<P> item(n); // value-weight
		item[0] = MP(0,0);
		FOR(i, 1, n){
			scanf("%d,%d", &item[i].first, &item[i].second);
		}
		vector<vector<int> > v(n, vector<int>(w+1, 0));

		FOR(i, 1, n){
			for(int j = 0; j+item[i].second <= w; j++){
				v[i][j+item[i].second] = max( v[i-1][j+item[i].second], v[i-1][j]+item[i].first );
			}
		}

		int idx = 0;
		rep(i, w+1){
			if(v[n-1][idx] < v[n-1][i]){
				idx = i;
			}
		}

		cout << "Case " << ++casenum << ':' << endl;
		cout << v[n-1][idx] << endl;
		cout << idx << endl;
	}

	return 0;
}