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
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <complex>
#include <math.h>

using namespace std;

//conversion
//------------------------------------------
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();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<long, long> PLL;
typedef long long LL;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(long i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

const long double EPS = 1e-12;
const LL INF = 1e18;


int dp[1002][1001];
int w[1001],v[1001];


int main(){
	int maxw,N;
	int cnt=1;
	while(cin>>maxw){
		if(maxw==0)break;
		cin>>N;
		CLR(dp);
		char c;
		REP(i,N)cin>>v[i]>>c>>w[i];
		int res1=0,res2=10000;
		REP(i,N){
			REP(j,maxw+1){
				if(j+w[i]<=maxw){
					dp[i+1][j+w[i]]=max(dp[i+1][j+w[i]],dp[i][j]+v[i]);
					if(dp[i+1][j+w[i]]>res1){
						res1=dp[i+1][j+w[i]];
						res2=j+w[i];
					}else if(dp[i+1][j+w[i]]==res1){
						res2=min(res2,(int)j+w[i]);
					}
				}
			}
		}
		cout<<"Case "<<cnt<<":"<<endl;
		cout<<res1<<endl;
		cout<<res2<<endl;
	}
	return 0;
}
/*

*/

C++: #include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
  int cas=0;
  int anskati=0;
  int ansomo;
  int w,n;
  int kati[1111],omo[1111];
  int memo[1111][1111];
  while(1){
    cas++;
    cin>>w;
    if(w==0) break;
    cin>>n;
    for(int i=0;i<=w;i++){
      memo[0][i]=0;
    }
    for(int i=0;i<n;i++){
      char a;
      cin>>kati[i]>>a>>omo[i];
    }
    cout<<"Case "<<cas<<':'<<endl;
    
    for(int i=1;i<=n;i++){
      for(int j=1;j<=w;j++){
	if(j<omo[i-1]){
	  memo[i][j]=memo[i-1][j];
	}else{
	  memo[i][j]=max(memo[i-1][j],memo[i-1][j-omo[i-1]]+kati[i-1]);
	}
      }
    }
    for(int i=0;i<=w;i++){
      if(memo[n][i]>anskati){
	anskati=memo[n][i];
	ansomo=i;
      }
    }
    cout<<anskati<<endl;
    cout<<ansomo<<endl;
    
  }
}

C++: #include<stdio.h>
#include<string.h>
#include<math.h>
int a,s,d[1001],f[1001],g[1001][1001],h,i,j,z,x=1;
int main(void)
{
	while(1){
		scanf("%d",&a);
		if(a==0)	break;
		scanf("%d",&s);
		for(i=0;i<s;i++)
			scanf("%d,%d",&d[i],&f[i]);
		for(i=0;i<s;i++){
			for(j=0;j<a;j++)
				g[i][j]=-1;
		}
		g[0][0]=0;
		for(i=0;i<s;i++){
			for(j=0;j<=a;j++){
				if(g[i][j]!=-1){
					if(g[i][j]>g[i+1][j])
						g[i+1][j]=g[i][j];
					if(j+f[i]<=a){
						if(g[i][j]+d[i]>g[i+1][j+f[i]])
							g[i+1][j+f[i]]=g[i][j]+d[i];
					}
				}
			}
		}
		h=0;
		for(i=0;i<=a;i++){
			if(h<g[s][i]){
				h=g[s][i];
				z=i;
			}
		}
		printf("Case %d\n",x);
		printf("%d\n%d",h,z);
		x++;
	}
	return 0;
}

C++: #include<stdio.h>

int main()
{
	for(int c=1;;c++)
	{
		int w,n,kati[100],weit[100],weitk=0,katik=0;
		while(scanf("%d",&w))
		{
			if(w==0)
			{
				return 0;
			}
			else if(w>1000)
			{
			}
			else
			{
				break;
			}
		}

		scanf("%d",&n);
		
		int katisum[100][100]={0},weitsum[100][100]={0};
		for(int x=0;x<n;x++)
		{
			scanf("%d,%d",&kati[x],&weit[x]);
		}
		for(int y=0;y<n;y++)
		{
			for(int z=y;z<n;z++)
			{
				for(int r=y;r<=z;r++)
				{
					katisum[y][z]+=kati[r];
					weitsum[y][z]+=weit[r];
				}
			}
		}

		for(int y=0;y<n;y++)
		{
			for(int z=0;z<n;z++)
			{
				if(w>=weitsum[y][z]&&katik<katisum[y][z])
				{
					weitk=weitsum[y][z];
					katik=katisum[y][z];
				}
				
			}
		}
		for(int y=0;y<n;y++)
		{
			for(int z=0;z<n;z++)
			{
				if(katik==katisum[y][z]&&weitk>weitsum[y][z])
				{
					weitk=weitsum[y][z];
				}
			}
		}
		printf("Case %d:\n%d\n%d\n",c,katik,weitk);
	}
}

C++: #include <bits/stdc++.h>

using namespace std;

#define MAX 1024

int main()
{
    int W, N, T = 1;
    while (cin >> W, W) {
        cin >> N;
        char c;
        vector<int> v(N), w(N);
        for (int i = 0; i < N; i++) {
            cin >> v[i] >> c >> w[i];
        }

        int dp[MAX] = {};
        for (int i = 0; i < N; i++) {
            for (int j = W; j >= w[i]; j--) {
                dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
            }
        }
        
        int max_v = *max_element(dp, dp + W + 1), min_w = -1;
        for (int i = W; i >= 0; i--) {
            if (dp[i] == max_v) {
                min_w = i;
            }
        }        
        cout << "Case " << T++ << ":" << endl;
        cout << max_v << endl;
        cout << min_w << endl;
    }
    return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;

int table[1001];

int main(){
  int C;
  for(int i=1; cin>>C, C; ++i)
  {
    for (int k = 0; k < 1001; ++k) table[k] = -1e9;
    table[0] = 0;

    int n; cin >> n;
    for(;n--;) {
      int v, w; char comma;
      cin >> v >> comma >> w;
      for (int k = 1000 - w; k >=0; --k) { // table の上から更新
        table[k+w] = max<int>(table[k+w], table[k] + v);
      }
    }

    int W, V=table[0];
    for (int k = 0; k <= C; ++k) { // 最小のインデクスを答える必要
      if (V < table[k]) {
        V = table[k];
        W = k;
      }
    }

    printf("Case %d:\n%d\n%d\n", ++i, V, W);
  }
}