Go: package main

import (
	"bufio"
	"os"
	"strconv"
	"strings"
	"fmt"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	Case := 1
	for {
		scanner.Scan()
		W, _ := strconv.Atoi(scanner.Text())
		if W == 0 {
			break
		}
		scanner.Scan()
		n, _ := strconv.Atoi(scanner.Text())
		w := make([]int, n+1)
		v := make([]int, n+1)
		for i := 1; i <= n; i++ {
			scanner.Scan()
			info := strings.Split(scanner.Text(), ",")
			v[i], _ = strconv.Atoi(info[0])
			w[i], _ = strconv.Atoi(info[1])
		}
		// fmt.Println(v)
		// fmt.Println(w)
		dp := make([][]int, n+1)
		for i := range dp {
			dp[i] = make([]int, W+1)
		}
		maxV := -(1 << 21)
		minW := 1 << 21
		for i := 1; i <= n; i++ {
			for j := 1; j <= W; j++ {
				// fmt.Println(dp)
				if j-w[i] >= 0 {
					dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])
					if maxV < dp[i][j] {
						maxV = dp[i][j]
						minW = j
					} else if maxV == dp[i][j] {
						minW = min(minW, j)
					}
				} else {
					dp[i][j] = dp[i-1][j]
				}
			}
		}
		fmt.Printf("Case %d:\n", Case)
		Case += 1
		fmt.Println(maxV)
		fmt.Println(minW)
	}
}
func max(x, y int) int {
	if x < y {
		return y
	}
	return x
}
func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

C++: #include<stdio.h>
int i,j,l;
int w;
int n;
int a;
int kati,omosa;
int casecnt=0;
int maxkati,maxomosa;
long long int dp[1000][10000];//dp[お宝の総数][お宝の重さ]
int main(void){
	scanf("%d",&w);
	while(w!=0){
		for(i=0;i<=1000;i++){
			for(j=0;j<=10000;j++){
				dp[i][j]=0;
			}
		}
		scanf("%d",&n);
		scanf("%d%c%d",&kati,&a,&omosa);
		dp[0][omosa]=kati;
		for(j=1;j<=n;j++){
			dp[j][omosa]=dp[0][omosa];
		}
		for(i=1;i<n;i++){
			scanf("%d%c%d",&kati,&a,&omosa);
			for(j=i;j<=n;j++){
				if(dp[j][omosa]<kati){
					dp[j][omosa]=kati;
				}
			}
			for(j=1;j<=w;j++){
				if(dp[i-1][j]>0){
					dp[i][j+omosa]=dp[i-1][j]+kati;
					for(l=i;l<=n;l++){
						if(dp[i-1][j+omosa]>dp[l+1][j+omosa]);
						else {
							dp[l][j+omosa]=dp[i][j+omosa];
						}
					}
				}
			}
			for(j=i;j<=w;j++){
				if(dp[i][j+omosa]>dp[j+1][j+omosa]){
					dp[j+1][j+omosa]=dp[i][j+omosa];
				}
			}
		}
		/*for(i=0;i<=n;i++){
			for(j=1;j<=w;j++){
				printf("%d ",dp[i][j]);
			}
			printf("\n");
		}*/
		maxomosa=0;
		maxkati=0;
		for(j=0;j<=w;j++){
			if(maxkati<dp[n][j]){
				maxkati=dp[n][j];
				maxomosa=j;
			}
		}
		casecnt++;
		printf("case %d:\n",casecnt);
		printf("%d\n",maxkati);
		printf("%d\n",maxomosa);
		scanf("%d",&w);
	}
	return 0;
}

C++: #include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <map>
#define INF 100000000
#define rep(i,a) for(int i=0;i<(a);i++)

using namespace std;
typedef long long ll;

int dp[2000][20000];    //dp[i][j]  i番目以前の物で、重さがj以下の時の価値
int W[2000],V[2000];

int w,n;

void solve(){
    for(int i=n-1;i>=0;i--){
        for(int j=0;j<=w;j++){
            if(j-W[i]<0){
                dp[i][j]=dp[i+1][j];
            }
            else{
                dp[i][j]=max(dp[i+1][j],dp[i+1][j-W[i]]+V[i]);
            }
            
        }
    }
    
    cout<<dp[0][w]<<endl;
    for(int i=w;i>=1;i--){
        if(dp[0][i]!=dp[0][i-1]){
            cout<<i<<endl;
            break;
        }
    }
}

int main(){
    int count=1;
    while(1){
        memset(dp,0,sizeof(dp));
    
        cin>>w>>n;
        if(w==0)break;
        char a;
        rep(i,n)cin>>V[i]>>a>>W[i];
    
        cout<<"Case "<<count<<":"<<endl;
        count++;
        solve();
    }
    return 0;
}

C++: #include<stdio.h>
int i,j,l;
int w;
int n;
int a;
int kati,omosa;
int casecnt=0;
int maxkati,maxomosa;
long long int dp[10000][10000];//dp[お宝の総数][お宝の重さ]
int main(void){
	scanf("%d",&w);
	while(w!=0){
		for(i=0;i<=1000;i++){
			for(j=0;j<=10000;j++){
				dp[i][j]=0;
			}
		}
		scanf("%d",&n);
		scanf("%d%c%d",&kati,&a,&omosa);
		dp[0][omosa]=kati;
		for(j=1;j<=n;j++){
			dp[j][omosa]=dp[0][omosa];
		}
		for(i=1;i<n;i++){
			scanf("%d%c%d",&kati,&a,&omosa);
			for(j=i;j<=n;j++){
				if(dp[j][omosa]<kati){
					dp[j][omosa]=kati;
				}
			}
			for(j=1;j<=w;j++){
				if(dp[i-1][j]>0){
					dp[i][j+omosa]=dp[i-1][j]+kati;
					for(l=i;l<=n;l++){
						if(dp[i-1][j+omosa]>dp[l+1][j+omosa]);
						else {
							dp[l][j+omosa]=dp[i][j+omosa];
						}
					}
				}
			}
			for(j=i;j<=w;j++){
				if(dp[i][j+omosa]>dp[j+1][j+omosa]){
					dp[j+1][j+omosa]=dp[i][j+omosa];
				}
			}
		}
		/*for(i=0;i<=n;i++){
			for(j=1;j<=w;j++){
				printf("%d ",dp[i][j]);
			}
			printf("\n");
		}*/
		maxomosa=0;
		maxkati=0;
		for(j=0;j<=w;j++){
			if(maxkati<dp[n][j]){
				maxkati=dp[n][j];
				maxomosa=j;
			}
		}
		casecnt++;
		printf("case %d:\n",casecnt);
		printf("%d\n",maxkati);
		printf("%d\n",maxomosa);
		scanf("%d",&w);
	}
	return 0;
}

C++: #include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int W,N,w[1001],v[1001],ansW,ansV;
int memo[1001];
void func(int i,int j,int _v){
    //printf(" %d,%d,%d\n",i,j,_v);
    if(memo[j]>_v){
        return;
    }
    memo[j] = _v;
    if(i==N){
        if(ansV<_v){
            ansV = _v;
            ansW = j;
        }
        else if(ansV==_v && ansW>j){
            ansV = _v;
            ansW = j;
        }
        return;
    }
    //ans2=max(ans2,j);
    if(j+w[i]<=W) func(i+1,j+w[i],_v+v[i]);
    func(i+1,j,_v);
    //ans2=max(ans2,j);
}
int main(){
    int tc=1;
    while(cin>>W,W){
        fill(memo,memo+1001,0);
        ansW=ansV=0;
        cin>>N;
        for(int i=0;i<N;i++){
            scanf("%d,%d",&v[i],&w[i]);
        }
        func(0,0,0);
        cout<<"Case "<<tc<<":"<<endl<<ansV<<endl<<ansW<<endl;;
        tc++;
    }
}

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

#define fir first
#define sec second

typedef pair <int, int> P;
vector <P> v(1028);

int dp[1028][2048];

int main(void)
{
	int cnt = 1;
	while (1){
		int w, n;
		cin >> w; if (w == 0) break;
		cin >> n;
		char a;
		for (int i = 0; i < n; i++){
			scanf("%d,%d", &v[i].fir, &v[i].sec);
		}
		for (int i = 0; i < n; i++){
			for (int j = 0; j <= w; j++){
				if (j < v[i].sec) dp[i+1][j] = dp[i][j];
				else dp[i+1][j] = max(dp[i][j], dp[i][j-v[i].sec]+v[i].fir);
			}
		}
		int res1 = 0, res2 = 0;
		for (int i = 1; i <= w; i++){
			if (res1 < dp[n][i]){
				res1 = dp[n][i];
				res2 = i;
			}
		}
		cout << "Case " << cnt << ":" << endl << res1 << endl << res2 << endl;
		cnt++;
	}
	return 0;
}

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

int W,N;
int dp[1001][1001]; // 宝の数×重さ
struct Obj {
	int price;
	int weight;
} obj[1001];

int main(void){
	int cnt = 1;
	while (cin >> W, W) {
		// input
		cin >> N;
		char buf;
		for (int i = 0; i < N; i++) {
			cin >> obj[i].price >> buf >> obj[i].weight;
		}
		
		// init
		for (int i = 0; i < N; i++) {
			for (int j = 0; j <= W; j++) {
				dp[i][j] = 0;
			}
		}
		dp[0][obj[0].weight] = obj[0].price;

		// calc
		int wei;
		for (int i = 0; i < N - 1; i++) {
			for (int j = 0; j <= W; j++) {
				if (j != 0 && dp[i][j] == 0) {
					continue;
				}
				// 下
				dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
				// 右下
				if (wei = j + obj[i + 1].weight, wei <= W) {
					dp[i + 1][wei] = max(dp[i + 1][wei], dp[i][j] + obj[i + 1].price);
				}
			}
		}
		
		struct Obj res = {0, 0};
		for (int i = 0; i <= W; i++) {
			for(int j = 0; j < N; j++) {
				if (res.price < dp[j][i]) {
					res.price = dp[j][i];
					res.weight = i;
				}
			}
		}

		// output
		printf("Case %d:\n%d\n%d\n", cnt++, res.price, res.weight);
	}

	return 0;
}