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++: #define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<algorithm>
#define W_MAX 1000
#define N_MAX 1000

int W, N, dp[N_MAX + 1][W_MAX + 1], w[N_MAX + 1], v[N_MAX + 1];

int main(){
	int c = 1;
	while (1){
		scanf("%d %d", &W, &N);
		if (W == 0)
			break;
		for (int i = 1; i <= N; ++i){
			char ch = ',';
			scanf("%d %s %d", &v[i], &ch, &w[i]);
		}
		for (int i = 1; i <= W; ++i)
			dp[0][i] = 0;
		for (int i = 1; i <= W; ++i){
			for (int j = 1; j <= N; ++j){
				if (i < w[j])
					dp[i][j] = dp[i][j - 1];
				else{
					dp[i][j] = std::max(dp[i][j - 1], dp[i - w[j]][j - 1] + v[j]);
				}
			}
		}
		int minv = 1;
		for (int i = 0; i <= W; ++i){
			if (dp[i][N] < dp[i][N])
				minv = i;
		}
		printf("%s %d %s\n", "Case", c, ":");
		printf("%d\n", dp[N][W]);
		printf("%d\n", minv);
		++c;
	}
	return 0;
}

C++: #include<iostream>

using namespace std;

class item
{
public:
	int value;
	int weight;
	bool flag;
	item()
	{
		flag=false;
	}
};

bool input(int *c, int *n, item it[1000])
{
	cin>>*c;
	if(*c==0)
	{
		return false;
	}
	cin>>*n;
	for(int i=0;i<*n;i++)
	{
		char t;
		cin>>it[i].value>>t>>it[i].weight;
		it[i].flag=false;
	}
	return true;
}

item max(item a, item b)
{
	if(a.value>b.value)
	{
		return a;
	}
	else
	{
		return b;
	}
}

item add(item a, item b)
{
	a.value+=b.value;
	a.weight+=b.weight;
	return a;
}

item table[1000][1000];

item solve(int c, int n, item it[1000])
{
	if(table[c][n].flag!=true){
		if(c==0||n==0)
		{
			table[c][n].value=0;
			table[c][n].weight=0;
		}
		else if(c<it[n-1].weight)
		{
			table[c][n]=solve(c,n-1,it);
		}
		else
		{
			table[c][n]=max(solve(c,n-1,it),add(solve(c-it[n-1].weight,n-1,it),it[n-1]));
		}
		table[c][n].flag=true;
	}
	return table[c][n];
}

int main(void)
{
	for(int i=1;;i++)
	{	
		int c,n;
		item it[1000];
		if(input(&c,&n,it)==false)
		{
			break;
		}
		item ans=solve(c,n,it);
		cout<<"Case "<<i<<':'<<endl<<ans.value<<endl<<ans.weight<<endl;
		for(int i=0;i<1000;i++)
		{
			for(int j=0;j<1000;j++)
			{
				table[i][j].flag=false;
				table[i][j].value=0;
				table[i][j].weight=0;
			}
		}
	}
}

C++: #include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define REP(i,n) for(int i=0;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<29
#define LINF LLONG_MAX/3
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(v) (v).begin(),(v).end()
#define all(v) ALL(v)
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
#define CININIT cin.tie(0),ios::sync_with_stdio(false)
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

void solve(int W,int N){
    vector<int> v(N),w(N);
    rep(i,N) scanf("%d,%d",&v[i],&w[i]);

    vector<vector<int>> dp(N+10,vector<int>(W+10,0));
    for(int i=0;i<N;i++){
        // use v[i],w[i]
        for(int j=0;j<W;j++){
            if(j+w[i]<=W){
                dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]],dp[i][j]+v[i]);
                dp[i+1][j] = max(dp[i+1][j],dp[i][j]);
            }else{
                dp[i+1][j] = max(dp[i+1][j],dp[i][j]);
            }
        }
    }

    for(int i=0;i<=W;i++) if(dp[N][i]==dp[N][W]){
        printf("%d\n%d\n",dp[N][W],i);
        return;
    }
    assert(false);
}

int main(){
    int W,N;
    int cnt=0;
    while(1){
        scanf("%d",&W);
        if(W==0) break;
        scanf("%d",&N);
        printf("Case %d:\n",++cnt);
        solve(W,N);
    }
}

C++: #include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <utility>
#define mp make_pair
#define f first
#define s second
#define dm(x) cerr << #x << " = " << x << endl;
using namespace std;

#define rep(i,n) for(int i=0; i<(n); i++)
typedef pair<long,long> pp;

pp dp[1000][1000];
int p[1001],w[1001];
int W, N;

pp operator+(pp a,pp b)
{
  pp ret(a.f+b.f, a.s+b.s);
  return ret;
}

//i番目以降でj以下の重さで価値を最大化。 {最大の価値, その時の重さ}
pp calc(int i,int j)
{
  pp ret;
  if(dp[i][j].f>=0) return dp[i][j];
  if(i==N) ret=mp(0,0);
  else if(j<w[i]) ret=calc(i+1,j);
  else{
    pp a=calc(i+1,j);
    pp b=calc(i+1,j-w[i]) + mp(p[i],w[i]);
    if(a.f>b.f) ret = a;
    else if(a.f<b.f) ret = b;
    else{
      if(a.s > b.s) ret = b;
      else ret = a;
    }
  } 
  return dp[i][j] = ret;
}

int main()
{
  int n=1;
  while(scanf("%d", &W),W){
    scanf("%d", &N);
    rep(i,N) scanf("%d, %d",p+i, w+i);
    // rep(i,N) printf("%d: p:%d w:%d\n",i , p[i], w[i]);
    rep(i,N+1) rep(j,W+1) {dp[i][j]=mp(-1,-1);}
    pp ret=calc(0,W);
    // printf(","); rep(j,W+1) printf("%d,",j); printf("\n");
    // rep(i,N+1){
    //   printf("%d,",i);
    //   rep(j,W+1)
    //     printf("%d,",calc(i,j).f);
    //   printf("\n");
    // }
    // rep(i,N+1){
    //   printf("%d,",i);
    //   rep(j,W+1)
    //     printf("%d,",calc(i,j).s);
    //   printf("\n");
    // }
    
    printf("Case %d:\n%ld\n%ld\n", n++, ret.f, ret.s);
  }
  return 0;
}

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

const int MAX_N = 1000;
const int MAX_W = 10000;
int W, N;
int v[MAX_N];
int w[MAX_N];
int dp[MAX_N + 1][MAX_W + 1];

void printtable() {
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= W; j++) {
			printf("%4d", dp[i][j]);
		}
		printf("\n");
	}
}

void solve() {
	memset(dp, 0, sizeof(dp));
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= W; j++) {
			if (j - w[i] >= 0) {
				dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j]);
			}
			else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	printf("%d\n", dp[N][W]);
	for (int i = W; i >= 0; i--) {
		if (dp[N][W] != dp[N][i]) {
			printf("%d\n", i + 1);
			break;
		}
	}
}

int main () {
	int i = 0;
	while (scanf("%d", &W), W) {
		i++; printf("Case %d:\n", i);
		scanf("%d", &N);
		for (int i = 0; i < N; i++) {
			scanf("%d,%d", &v[i], &w[i]);
		}
		solve();
	}
	return 0;
}