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+1){
				dp[i][j] = max(dp[i][j],dp[i-1][j]);
				if(j-w[i-1]>=0)
					dp[i][j] = max(dp[i][j],dp[i-1][j-w[i-1]]+v[i-1] );

				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<<i<<" "<<j<<" "<<dp[i][j]<<endl;
			}
		}
		cout<<"Case "<<c<<":"<<endl;
		cout<<maxval<<endl;
		cout<<maxwait<<endl;
	}
}

C++: #include<stdio.h>
int a,b,c[1001][1001],d[1001],e[1001],m,mm,i,j,g=1;
int main(void)
{
	scanf("%d",&a);
	while(a!=0){
		m=0;
		mm=0;
		scanf("%d",&b);
		for(i=0;i<=b;i++){
			for(j=0;j<=a;j++){
				c[i][j]=-1;
				d[i]=0;
				e[i]=0;
			}
		}
		for(i=0;i<b;i++){
				scanf("%d,%d",&d[i],&e[i]);
		}
		c[0][0]=0;
		for(i=0;i<=b;i++){
			for(j=0;j<=a;j++){
				if(c[i][j]>=0 && c[i][j]+d[i]>c[i+1][j+e[i]] && j+e[i]<=a){
					c[i+1][j+e[i]]=c[i][j]+d[i];
				}
				if(c[i][j]>=0 && c[i+1][j]<c[i][j]){
					c[i+1][j]=c[i][j];
				}
			}
			
		}
		for(j=0;j<=a;j++){
			if(c[b][j]>m){
				m=c[b][j];
				mm=j;
				//printf("c=%d j=%d\n",c[b][j],j);
			}
		}
		/*for(i=0;i<=b;i++){
			for(j=0;j<=a;j++){
				printf("%4d",c[i][j]);
			}
			printf("\n");
		}
		printf("%d\n",c[b][49]);*/
		printf("Case %d:\n%d\n%d\n",g,m,mm);
		g++;
		scanf("%d",&a);
	}	
	return 0;
}

C++: #include<iostream>
#include<vector>
#include<cstring>
using namespace std;
#define TRESUREMAXNUM 1000
#define TRESUREMAXWEIGHT 1000

int dp[TRESUREMAXNUM+1][TRESUREMAXWEIGHT+1];
struct Tresure{
	int price;
	int weight;
};
Tresure tresureBox[TRESUREMAXNUM+1];
int
main(){
	int W,N;
	for(int i=1;cin>>W&&W;i++){
		memset(dp,-1,sizeof(dp));

		cin>>N;
		cout<<"Case "<<i<<":"<<endl;
		for(int j=1;j<=N;j++){
			char c;
			int w,p;
			cin>>p>>c>>w;
			tresureBox[j].price=p;tresureBox[j].weight=w;
		}
/*		cout<<"---list----"<<endl;
		for(int j=1;j<=N;j++)cout<<tresureBox[j].price<<","<<tresureBox[j].weight<<endl;
		cout<<"-----------"<<endl;*/
		dp[0][0]=0;
		for(int j=0;j<N;j++){
			for(int k=0;k<=W;k++){
				if(dp[j][k]==-1)continue;
				dp[j+1][k]=max(dp[j+1][k],dp[j][k]);

				if(k+tresureBox[j+1].weight<=W)dp[j+1][k+tresureBox[j+1].weight]=max(dp[j+1][k+tresureBox[j+1].weight]
				                                              ,dp[j][k]+tresureBox[j+1].price);
			}
		}
		int maxPrice=-1;
		int maxWeight=-1;
		for(int j=0;j<=W;j++){
			if(dp[N][j]==-1)continue;
			if(maxPrice<dp[N][j]){
				maxPrice=dp[N][j];
				maxWeight=j;
			}
		}
//		cout<<"##ans##"<<endl;
		cout<<maxPrice<<endl<<maxWeight<<endl;
	}
	return 0;
}

C++: 
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <memory>
#include <string>

#include <algorithm>
#include <complex>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>

using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
#endif

#define ITER(c)         __typeof__((c).begin())
#define FOREACH(it, c)  for (ITER(c) it=(c).begin(); it != (c).end(); ++it)
#define RITER(c)        __typeof__((c).rbegin())
#define RFOREACH(it, c) for (RITER(c) it=(c).rbegin(); it != (c).rend(); ++it)
#define REP(i, n)       REPEAT(i, 0, n)
#define REPEAT(i, k, n) for (int i = (k); i < (n); ++i)
#define REVREP(i, n)    for (int i = ((n)-1); i >= 0; --i)
#define FIND(c, n)      std::find((c).begin(), (c).end(), (n));
#define BSEARCH(c, n)   std::binary_search((c).begin(), (c).end(), (n))
#define LLPOW(p1,p2)    ((ll)pow((double)(p1), (int)p2))
#define ESIZEOF(A)      (sizeof(A)/sizeof((A)[0]))
#define MIN(p1,p2)      (((p1)<(p2))?(p1):(p2))
#define MAX(p1,p2)      (((p1)>(p2))?(p1):(p2))
#define CIN_NO_SYNC     do { cin.tie(0); ios_base::sync_with_stdio(false); } while(0)
#define GETSTR(p)       fgets((p), sizeof(p), stdin)
#define CHOMP(p)        do{ char *_q = (p) + strlen(p)-1; if(*_q == '\n') *_q = 0; } while(0)

typedef long long ll;
typedef unsigned long long ull;

#ifdef _DEBUG
#define pf printf
#define pr(n) do { cout << #n " = " << (n) << endl; } while(0)
#else
#define pf(...) /* */
#define pr(...) /* */
#endif


int main(){

    for(int i = 1; ; i++){
        int w, n;
        cin >> w;
        if(w == 0) break;
        cin >> n;

        int dp[2][1010];
        memset(dp, -1, sizeof(dp));
        int i0 = 0, i1 = 1;
        dp[0][0] = 0;

        REP(l,n){
            int p1, w1; char dmy;
            cin >> p1 >> dmy >> w1;

            REP(j,w+1){
                if(dp[i0][j] < 0) continue;
                dp[i1][j] = MAX(dp[i1][j], dp[i0][j]);
                int j2 = j + w1;
                if(j2 <= w){
                    dp[i1][j2] = MAX(dp[i1][j2], dp[i0][j] + p1);
                }
            }
            swap(i0, i1);
            memset(dp[i1], -1, sizeof(dp[i1]));
        }

        int result_p = 0;
        int result_w = 0;
        REP(j,w+1){
            if(result_p < dp[i0][j]){
                result_p = dp[i0][j];
                result_w = j;
            }
        }
        cout << "Case " << i << ":" << endl;
        cout << result_p << endl;
        cout << result_w << endl;
    }

    return 0;
}

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

#define MAX_W (1000)
#define MAX_N (1000)

int W, N;
int v[MAX_N], w[MAX_N];
int dp[MAX_N + 1][MAX_W + 1];

int rec_dp(int i, int wei)
{
  if (dp[i][wei] != -1){
    return (dp[i][wei]);
  }

  int res;
  if (i == N){
    res = 0;
  }
  else if (wei < w[i]){
    res = rec_dp(i + 1, wei);
  }
  else {
    res = max(rec_dp(i + 1, wei), rec_dp(i + 1, wei - w[i]) + v[i]);
  }

  return (dp[i][wei] = res);
}
int main()
{
  int cnt = 0;

  while (scanf("%d", &W), W){
    memset(dp, -1, sizeof(dp));
    scanf("%d", &N);
    for (int i = 0; i < N; i++) scanf("%d,%d", &v[i], &w[i]);
    for (int i = 0;;i++){
      if (rec_dp(0, i) == rec_dp(0, W)){
        printf("Case %d:\n", ++cnt);
        printf("%d\n%d\n", rec_dp(0, i), i);
        break;
      }
    }
  }

  return (0);
}