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 <cstdlib>
#include <time.h>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <sstream>
#include <string>
#include <bitset>
using namespace std;
#define FOR(I,F,N) for(int I = F; I < (int)(N); I++)
#define rep(i, n) FOR(i, 0, n)
#define FIN(V) cout<<V<<endl
#define pb push_back
#define INF (1 << 28)
 
template<typename T>
void remove(vector<T>& vector, unsigned int index){
vector.erase(vector.begin() + index);
}
 
typedef pair<int, int> P;
typedef long long ll;
typedef priority_queue<int> pq;
int StrToInt(string);
string IntToStr(int);
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
 
int W, N;
int tres[1001];
int weig[1001];
int maxW, maxV;
map<int,int> dp[1001];
 
void dfs(int weight, int value, int index){
    if(weight > W)return;
    if(dp[weight][index]>value)return;
    dp[weight][index] = value;
    if(index == N){
        if(maxV < value){
            maxW = weight;
            maxV = value;
        }else if(maxV == value){
            if(maxW > weight){
                maxW = weight;
                maxV = value;
            }
        }
        return;
    }
    dfs(weight, value, index+1);
    dfs(weight+weig[index], value+tres[index], index+1);
}
 
 
int main(void){
    int cnt = 0;
    while(cin >> W, W){
        cnt++;
        cin >> N;
        maxW = 0;
        maxV = 0;
        // fill_n(tres, 1001, 0);
        // fill_n(weig, 1001, 0);
        rep(i,1000)dp[i].clear();
 
        rep(i,N){
            int n, w;
            scanf("%d,%d", &n, & w);
            tres[i] = n;
            weig[i] = w;
        }
 
        dfs(0,0,0);
        cout << "Case " << cnt << ":" << endl;
        cout << maxV << endl << maxW << endl;
    }
 
    return 0;
}
 
 
 
int StrToInt(string s){
    stringstream ss;
    ss << s;
    int val;
    ss >> val;
    return val;
}
string IntToStr(int i){
    stringstream ss;
    ss << i;
    return ss.str();
}

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

int main(){
    int W,N;
    int cnt=1;
    while(true){
        cin>>W;
        if(W==0)break;
        cin>>N;
        int treasure[N+1][2];
        for(int i=1;i<N+1;i++)
            scanf("%d,%d",&treasure[i][0],&treasure[i][1]);
        
        int table[N+1][W+1];
        for(int i=0;i<N+1;i++)
            for(int j=0;j<W+1;j++)
                table[i][j]=0;
        
        for(int i=1;i<N+1;i++){
            for(int j=1;j<W+1;j++){
                if(j<treasure[i][1]){table[i][j] = table[i-1][j];continue;}
                int new_value = table[i-1][j-treasure[i][1]] + treasure[i][0];
                table[i][j] = max(new_value,table[i-1][j]);
            }
        }

        int m=0,w=0;
        for(int i=0;i<W+1;i++){
            if(table[N][i]>m){m=table[N][i];w=i;}
        }
        cout<<"Case "<<cnt<<":"<<endl;
        cout<<m<<endl<<w<<endl;
        cnt++;
    }
    return 0;
}

C++: #include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
int dp[1001],N,v[1001],w[1001],W;
signed main(){
    for(int l=1;;l++){
        fill(dp,dp+1001,0);
        /*fill(v,v+100,0);
        fill(w,w+100,0);*/
        cin>>W;
        if(W==0)break;
        cin>>N;
        for(int i=0;i<N;i++){
            scanf("%lld,%lld",&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]);
            }
        }
        for(int i=W;i>=0;i--){
            if(dp[W]!=dp[i]){
                cout<<"Case "<<l<<":"<<endl<<dp[W]<<endl<<i+1<<endl;
                break;
            }
        }
    }
    return 0;
}

C++: #include <bits/stdc++.h>
#define rep(i,l,n) for(int i=l;i<n;i++)
#define rer(i,l,n) for(int i=l;i<=n;i++)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
#define pb(a) push_back(a)
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

vi v,w;
int n;
int dp[1010][1010];

int solve(int i,int j){
	if(dp[i][j]>=0) 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(){
	for(int l=1;;l++){
		int W,x,y;
		cin>>W;
		if(W==0) break;
		cin>>n;
		rep(i,0,n){
			scanf("%d,%d",&x,&y); v.pb(x); w.pb(y);
		}
		memset(dp,-1,sizeof(dp));
		int MAX=0,ans=0;
		rer(i,1,W){
			if(MAX<solve(0,i)){
				MAX=solve(0,i); ans=i;
			}
		}
		cout<<"Case "<<l<<":"<<endl; o(MAX); o(ans);
	}
}

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


int dp[MAX_N][MAX_W];
int n,W;
int w[MAX_N];
int v[MAX_N];

void solve(){
  memset(dp,0,sizeof(dp));
  cout<<"Case 1:"<<endl;
  for(int i=0;i<n;i++){
    for(int j=0;j<=W;j++){
      if(j>=w[i]){
	dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
      }else{
	dp[i+1][j]=dp[i][j];
      }
    }
  }
  cout << dp[n][W] << endl;
  int tmp=0;
  int weight;
  for(int i=0;i<=W;i++){
    if(dp[n][i]>tmp){
      tmp=dp[n][i];
      weight=i;
    }
  }
cout << weight << endl;
}

int main(){
  while(cin>>W,W){
    cin>>n;
    for(int i=0;i<n;i++){
      scanf("%d,%d",&v[i],&w[i]);
    }
    solve();
  }

  return 0;
}