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<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>
#include<set>
 
using namespace std;
 
#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define F(i,j,k) fill(i[0],i[0]+j*j,k)
#define P(p) cout<<(p)<<endl;
#define INF 1<<25
 
typedef long long ll;

int dy[8]={1,1,1,0,0,-1,-1,-1};
int dx[8]={-1,0,1,-1,1,-1,0,1};
struct S{
	int a,b,c;
};
bool asc(const S& left,const S& right){
	return left.c > right.c;
}

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

int main(){
	int cnt=1;
	while(cin>>W){
		if(W==0)break;
		cin>>N;
		rep(i,N)cin>>v[i]>>w[i];
		REP(i,1,N+1){
			rep(j,W+1){
				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 ans_v=0,ans_w=0;
		rep(i,W+1){
			if(dp[N][i]>ans_v){
				ans_v=dp[N][i];
				ans_w=i;
			}
		}
		cout<<"Case "<<cnt<<":"<<endl;
		cout<<ans_v<<endl;
		cout<<ans_w<<endl;
		cnt++;
	}
	return 0;
}

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[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 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<algorithm>
#include<cstdio>
using namespace std;

int dp[1001][1001];

int main()
{
	int c = 1;

	while(1)
	{

		memset(dp, 0, sizeof(dp));

		int w, n;
		cin>>w>>n;
		if(w == 0)break;
		int treasure[1000];
		int price[1000];

		for(int i = 0; i < n; i++)
			scanf("%d,%d", &price[i], &treasure[i]);

		for(int i = 0; i < n; i++){
			for(int j = 0; j <= w; j++){
				if(j < treasure[i])
					dp[i + 1][j] = dp[i][j];
				else
					dp[i + 1][j] = max(dp[i][j], dp[i][j - treasure[i]] + price[i]);
			}
		}
	
		int ansWeight;
		for(ansWeight = w - 1; w >= 0; ansWeight--)
			if(dp[n][w] > dp[n][ansWeight])break;
			
		cout << "Case" << c++ <<":"<<endl;
		cout << dp[n][w] << endl;
		cout << ansWeight + 1 << endl;
	}

	return 0;
}

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

int main(){
	int w, cntcase = 1;
	while (cin >> w, w){
		int n, dp[1000], treas_val, treas_w, ans_val = 0, ans_w = 0;
		cin >> n;
		for (int i = 0; i < w; i++) dp[i] = -1;
		dp[0] = 0;
		for (int i = 0; i < n; i++){
			scanf("%d,%d", &treas_val, &treas_w);
			for (int i = w - 1; i >= 0; i--){
				if (dp[i] != -1 && i + treas_w < w){
					dp[i + treas_w] = dp[i] + treas_val;
				}
			}
		}
		for (int i = 0; i < w; i++){
			if (ans_val < dp[i]){
				ans_val = dp[i];
				ans_w = i;
			}
		}
		printf("Case %d:\n%d\n%d\n", cntcase, ans_val, ans_w);
		cntcase++;
	}
	return 0;
}

C++: #include<cstdio>
#include<algorithm>
using namespace std;
int W,N,c;
int w[1024],p[1024],dp[2][10001];

int main(void){
	while(scanf("%d",&W)&&W){
		int ans;
		scanf("%d",&N);
		for(int i = 1; i <= N; i++){
			scanf("%d,%d", &p[i], &w[i]);
		}
		printf("%d %d\n",w[1],p[1]);
		for(int i = 1; i <= N; i++){
			for(int j = 1;j <= W; j++){
				if(j-w[i]<0)continue;
				dp[i%2][j] = max(dp[1-i%2][j],dp[1-i%2][j-w[i]]+p[i]);
			}
		}
		printf("Case%2d:\n",++c);
		printf("%d\n",dp[N%2][W]);
		for(int i = 1; i <= W; i++){
			if(dp[N%2][W] == dp[N%2][i]){
				ans = i;
				break;
			}
		}
		
		printf("%d\n",ans);
		/*ツ渉可甘コツ可サ*/
		for(int i = 0; i < 1024; i++)w[i] = p[i] = 0;
		for(int i = 0; i < 2; i++)for(int j = 0; j < 10001; j++)dp[i][j] = 0;
	}
	return 0;
}

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

using namespace std;

const int N = 1000;

int w, n;
int weight[N];
int value[N];
int dp[N+1][N+1];

void solve(){
   fill(dp[0], dp[N+1], -1);
   for(int i=0;i<N+1;i++){
      dp[0][i] = 0;
   }
   for(int i=0;i<n;++i){
      for(int j=0;j<=w;++j){
         if(j < weight[i]){
            dp[i+1][j] = dp[i][j];
         }else{
            dp[i+1][j] = max(dp[i][j], dp[i][j-weight[i]] + value[i]);
         }
      }
   }
   for(int i=w-1;i>=0;--i){
      if(dp[n][i] != dp[n][w]){
         cout << dp[n][w] << endl << i+1 << endl;
         return;
      }
   }
}

main(){
   for(int t=1;cin >> w && w;++t){
      cin >> n;
      for(int i=0;i<n;++i){
         char c;
         cin >> value[i] >> c >> weight[i];
      }
      cout << "Case " << t << ":" << endl;
      solve();
   }
   return 0;
}