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<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,x,n) for(int i=x;i<n;i++)
#define pb push_back
#define MAX 100005
#define int long long
using namespace std;
const int MOD=1000000007;
const int INF=1000000009;



signed main(){
  int W,N;
  int c=1;
  while(cin>>W>>N,W){
    vector<int> v(N),w(N);
    char x;
    vector<vector<int> > dp(N+1,vector<int>(W+1));
    rep(i,N)cin>>v[i]>>x>>w[i];
    loop(i,1,N+1){
      rep(j,W+1){
        if(j-w[i-1]>=0){
          dp[i][j]=max(dp[i-1][j-w[i-1]]+v[i-1],dp[i-1][j]);
        }else{
          dp[i][j]=dp[i-1][j];
        }
      }
    }
    int val=dp[N][W],wei;
    rep(i,W+1){
      if(dp[N][i]==val)wei=i;
    }
    cout<<"Case "<<c<<':'<<endl;
    cout<<val<<endl;
    cout<<wei<<endl;
    c++;
  }

  return 0;
}

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

using namespace std;

int main( void )
{
	int map[1001], save[1001];
	int w; long long count;
	count = 1;
	while(cin >> w, w) {
		++w;
		for(int i=0; i < w; ++i) map[i] = save[i] = 0;
		int n, value, weight;
		cin >> n;
		scanf("%d,%d", &value, &weight);
		save[weight] = map[weight] = max(save[weight], value);
		for(int i=1; i < n; ++i) {
			scanf("%d,%d", &value, &weight);
			save[weight] = max(save[weight], value);
			for(int j=0; j < w; ++j) {
				if(map[j]) {
					int ww = j + weight;
					if(ww < w)
						save[ww] = max(save[ww], map[j] + value);
					save[j] = max(save[j], map[j]);
				}
			}
			for(int j=0; j < w; ++j) {
				map[j] = save[j]; save[j] = 0;
			}
		}
		int Max = 0, idx;
		for(int i=1; i < w; ++i) {
			if(Max < map[i]) {
				Max = map[i];
				idx = i;
			}
		}
		cout << "Case " << count++ << ':' << endl;
		cout << Max << endl;
		cout << idx << endl;
	}

	return 0;
}

C++: #include <iostream>
#include <map>
#include <stdio.h>
int main(){
  using std::cin;
  using std::cout;
  using std::endl;
  using std::map;
  int weight,n,w,v,s,c=1;
  map<int,int> m;
  while(cin>>weight){
    if(!weight)return 0;
    cin>>n;
    map<int,int>::iterator it;
    for(;n;n--){
      scanf("%d,%d",&v,&w);
      if(m.empty()){m[w]=v;continue;}
      it = m.begin();
      while(it!=m.end()){
	s=(*it).second+v;
	  if((*it).first+w<weight){
	    if(m[(*it).first+w]<s)m[(*it).first+w]=(*it).second+v;
	  }
	it++;
      }
      m[w]=v;
    }
    it=m.end();
    it--;
    cout<<"Case "<<c++<<":"<<endl<<(*it).second<<endl<<(*it).first<<endl;
    m.clear();
  }
}

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

#define MAX 1001

int dp[MAX][MAX];
int v[MAX], w[MAX];

int main() {
	int W, n, u = 0;
	char t;
	while (cin >> W) {
		if (W == 0) break;
		cin >> n;
		u++;

		dp[MAX][MAX] = { 0 };
		for (int i = 0; i < n; i++) {
			cin >> v[i] >> t >> w[i];
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= W; j++) {
				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 mv = 0, mw;
		for (int i = 0; i <= W; i++) {
			if (dp[n][i] > mv) {
				mv = dp[n][i];
				mw = i;
			}
		}

		cout << "Case " << u << ":" << endl;
		cout << mv << endl;
		cout << mw << endl;
	}
	return 0;
}

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

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(n) rep(i,n)
#define all(n) n.begin(),n.end()

const int MAXW = 1000, MAXN = 1000;

int dp[MAXN + 1][MAXW + 10];
int w[MAXN + 1];
int v[MAXN + 1];

int main()
{
    int wl, n, casen = 1;
    char t;
    while(cin >> wl && wl)
    {
        cin >> n; REP(n) cin >> v[i] >> t >> w[i];

        memset(dp, 0, sizeof(dp));
        dp[0][0] = 0;
        
        REP(n)rep(j,wl + 1)if(j + w[i] <= wl)
            dp[i+1][j + w[i]] = max(dp[i][j + w[i]], dp[i][j] + v[i]);
        
        int answ = 0, ansv = -1;
        REP(wl + 1)if(dp[n][i] != -1 && ansv < dp[n][i]){ ansv = dp[n][i]; answ = i;}
        cout << "Case " << casen << ":"<< endl;
        cout << ansv << endl;
        cout << answ << endl;
        casen++;
    }

    return 0;
}

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

int dp[1010][1010];

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

		for (int i = 0;i < n;i++)
			for (int j = 0;j < w;j++)dp[i][j] = -1;
		dp[0][0] = 0;

		for (int i = 0;i < n;i++) {
			for (int j = 0;j <= w;j++) {
				if (dp[i][j] !=-1) {
					dp[i + 1][j] = dp[i][j];
				if(j+m[i]<=w)	dp[i + 1][j + m[i]] = max(dp[i][j] + v[i], dp[i + 1][j + m[i]]);
				}
			}
		}

		int k=0, aw=0;
		for (int i = 0;i <= w;i++) {
			if (dp[n][i] > k) {
				k = dp[n][i];
				aw = i;
			}
		}
		cout << "Case " << x << ":" << endl;
		cout << k << endl << aw << endl;
		x++;
	}
	return 0;
}

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

int main()
{
    int wmax,n,m;
    int val,w;
    int t[1001];
    int i,j,c;
    c = 0;
    while(1)
    {
	cin >> wmax;
	if (wmax == 0)break;
	for (i=0; i<1001; i++)
	{
	    t[i]=0;
	}
	c++;
	m = 0;
	cin >> n;
	for (i=0; i<n; i++)
	{
	    scanf("%d,%d",&val,&w);
	    for (j=wmax; j>w; j--)
	    {
		if (t[j-w] != 0)
		{
		    t[j] = max(t[j],val+t[j-w]);
		    m = max(m,t[j]);
		}
	    }
	    t[w] = max(t[w],val);
	    if (w<=wmax)
		m = max(m,val);
	}
	for (j=0; j<=wmax; j++)
	{
	    if (m==t[j])
		break;
	}
	cout << "Case " << c << ":" << endl;
	cout << m << endl;
	cout << j << endl;
    }
    return 0;
}