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<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<stack>
#include<queue>

using namespace std;

int main(){
	int N,W;
	int c=1;
	
	while(scanf("%d",&W)){
		if(W==0) break;
		scanf("%d",&N);
		
		vector<int> v(N);
		vector<int> w(N);
		vector<int> dp(10001,0);
		
		for(int i=0;i<N;i++){
			scanf("%d, %d",&v[i],&w[i]);
		}
		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]);
			}
		}
		printf("Case %d:\n",c);
		c++;
		printf("%d\n",*max_element(dp.begin(),dp.begin()+W+1));
		vector<int>::iterator maxit=max_element(dp.begin(),dp.begin()+W+1);
		printf("%ld\n",distance(dp.begin(),maxit));
	}
}

C++: #include<iostream>
#include<iomanip>
#include<queue>
#include<string>
#include<stack>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<utility>
#include<map>
#include<set>
#include<vector>
#include<functional>

using namespace std;

#ifdef DEBUG
#define dprintf      printf
#define dout(x)      cout<<#x" = "<<(x)<<endl
#define darray(x,n)    {int i;rep(i,n)cout<<#x"["<<i<<"] = "<<*((x)+i)<<endl;}
#define dloop(i,s,g) for((i)=(s);(i)<(g);(i)++)
#define drep(i,n)    for((i)=0;(i)<(n);(i)++)
#define dstop()      scanf("%*c")
#else
#define dprintf      (1)?0:printf
#define dout(x)
#define darray(x,n)
#define dloop(i,s,g) if(1){}else
#define drep(i,n)    if(1){}else
#define dstop()      if(1){}else
#endif

#define F    first
#define S    second
#define pb   push_back
#define mp   make_pair

#define loop(i,s,g) for((i)=(s);(i)<(g);(i)++)
#define rep(i,n)    for((i)=0;(i)<(n);(i)++)
#define all(x)      (x.begin(),x.end())
#define in(T,...) T __VA_ARGS__; impl(__VA_ARGS__);
#define array(T,id,n) T id[n]; rep(i,n)cin>>id[i];

//#define int long long;
#ifndef int
#define INF  (0x7fffffff)
#else
#define LINF (0x7fffffffffffffff)
#endif

typedef  long long           ll;
typedef  unsigned            ui;
typedef  unsigned long long  ull;
typedef  pair<int,int>       i_i;
typedef  pair<ll,int>        ll_i;
typedef  pair<ll,ll>         ll_ll;
typedef  pair<double,int>    d_i;
typedef  pair<double,double> d_d;

void impl(){};
template <typename T,typename... TS >
void impl(T &head,TS &... tail)
{
  cin>>head;
  impl(tail ...);
}




int dp[1123];
int W,n;
int v[1123];
int w[1123];

signed main(void)
{
  int i,j,k=0;

  while(1)
    {
      k++;
      rep(i,1123)dp[i]=0;
      int a=0;
      cin>>W;
      if(!W)break;
      cin>>n;
      rep(i,n)
	scanf("%d%*c%d",&v[i],&w[i]);
      rep(i,n)
	for(j=W;j>=w[i];j--)
	  dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
      rep(i,W+1)
	if(dp[i]>dp[a])a=i;
      printf("Case %d:\n%d\n%d\n",k,dp[a],a);
    }
  return 0;
}

C++: // DP
#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAX_N 1001
#define MAX_W 1001
using namespace std;

int main(){
	int caseNum = 1;
	int ans;
	int W, n;
	int v[MAX_N];
	int w[MAX_N];
	int dp[MAX_N][MAX_W];
	while(cin >> W){
		if(W == 0){
			break;
		}
		cin >> n;
		for (int i = 0; i < n; i++) {
			scanf("%d,%d", &v[i], &w[i]);
		}
		
		memset(dp, 0, sizeof(dp));
		for (int i = 0; i < n; i++){
			for (int j = 0; j <= W; j++){
				if(j < w[i]){
					dp[i+1][j] = dp[i][j];
				} else{
					dp[i+1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
				}
			}
		}
		// answer
		cout << "Case " << caseNum++ << ":" << endl;
		for (int i = W; i >= 0; i--) {
			if(dp[n][W] != dp[n][i]) {
				ans = i+1;
				break;
			}
		}
		cout << dp[n][W] << endl;
		cout << ans << endl;
	}
	return 0;
}

C++: #include <iostream>
#include <utility>
#include <vector>
#include <cstring>
using namespace std;
const int MAX_N = 1000,MAX_M = 1000;
int n;
typedef pair<int,int> P;
P ilist[MAX_N];
P memo[MAX_N + 1][MAX_M + 1];

P comp(const P &a,const P &b){
	if(a.first < b.first) return b;
	return a;
}

P dp(int now,int lim){
	if(memo[now][lim].first > -1){
		return memo[now][lim];
	}
	P res;
	if(now == n) return make_pair(0,0);
	else if(lim < ilist[now].second){
		res = dp(now + 1,lim);
	}
	else{
		res = dp(now + 1,lim - ilist[now].second);
		res.second += ilist[now].second;
		res.first += ilist[now].first;
		res = comp(dp(now + 1,lim),res);
	}
	return memo[now][lim] = res;
}

int main(){
	int lim,cnt = 0,w,v;
	P item;
	char buf;
	while(cin >> lim,lim){
		for(int i = 0;i <= MAX_N;++i){
			for(int j = 0;j <= MAX_M;++j){
				memo[i][j] = make_pair(-1,-1);
			}
		}
		++cnt;
		cin >> n;
		for(int i = 0;i < n;++i){
			cin >> v >> buf >> w;
			ilist[i] = make_pair(v,w);
		}
		item = dp(0,lim);
		cout << "Case " << cnt << ":" << endl;
		cout << item.first << endl << item.second << endl;
	}
	return 0;
}

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

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

int solve(int i, int j) {
	if (dp[i][j] != -1)return dp[i][j];

	int res;
	if (i == N)res = 0;
	else if (j < w[i])res = solve(i + 1, j);
	else {
		res = max(
			solve(i + 1, j),
			solve(i + 1, j - w[i]) + v[i]
		);
	}
	return dp[i][j] = res;
}

int main() {
	int now = 1;
	while (1) {
		cin >> W;
		if (W == 0)break;
		cin >> N;
		for (int i = 0; i < N; i++) {
			scanf_s("%d,%d", v + i, w + i);
		}

		for (int i = 0; i <= N; i++) {
			for (int j = 0; j <= W; j++) {
				dp[i][j] = -1;
			}
		}
		solve(0, W);
		for (int i = 0; i <= N; i++) {
			for (int j = 0; j <= W; j++) {
				cout << i << ":" << j<<"=" << dp[i][j] << endl;
			}
		}
		int value = -1; int weight;
		for (int i = 0; i <= W;i++) {
			if (value < dp[0][i]) {
				value = dp[0][i];
				weight = i;
			}
		}
		cout << "Case " << now++ << ":" << endl << value << endl << weight-1 << endl;
	}
}