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 <algorithm>
using namespace std;
int DP[1001][1001];
int main(){
	int W,N,C=0;
	while(cin>>W){
		if(!W) break;
		cin>>N;
		int v[1000],w[1000],SUMW=W;
		for(int i=0;i<N;++i) scanf("%d,%d",&v[i],&w[i]);
		for(int i=0;i<=N;++i)for(int j=0;j<=W;++j) DP[i][j]=0;
		for(int i=0;i<N;++i){
			for(int j=0;j<=W;++j){
				if(w[i]>j){//入らない時
					DP[i+1][j]=DP[i][j];
				}else{//入る時
					DP[i+1][j]=max(DP[i][j],DP[i][j-w[i]]+v[i]);
				}
			}
		}
		for(int j=W;j>=0;--j) if(DP[N][W]==DP[N][j])SUMW=j;
		cout<<"Case "<<++C<<":\n";
		cout<<DP[N][W]<<"\n"<<SUMW<<"\n";
	}
	return 0;
}

C++: #include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int W,N,w[1001],v[1001],ansW=0,ansV=0;
int memo[1001][1001],cou,ans2;
int func(int i,int j,int _v){
    //printf(" %d,%d,%d\n",i,j,_v);
    if(j>W)return 0;
    if(memo[i][j]>_v){
        return 0;
    }
    memo[i][j] = _v;
    if(i==N){
        if(ansV<_v){
            ansV = _v;
            ansW = j;
        }
        else if(ansV==_v && ansW>j){
            ansV = _v;
            ansW = j;
        }
        return _v;
    }
    //ans2=max(ans2,j);
    return max(func(i+1,j,_v),func(i+1,j+w[i],_v+v[i]));
    //ans2=max(ans2,j);
}
int main(){
    int tc=1;
    while(cin>>W,W){
        fill(*memo,*memo+1001*1001,0);
        int ans=0,cou=0;
        cin>>N;
        for(int i=0;i<N;i++){
            scanf("%d,%d",&v[i],&w[i]);
        }
        func(0,0,0);
        cout<<"Case "<<tc<<":"<<endl<<ansV<<endl<<ansW<<endl;;
        tc++;
    }
}

C++: #include<stdio.h>
int a,b,c[1001][1001],d[1001],e[1001],m,mm,i,j,g=1;
int main(void)
{
	scanf("%d",&a);
	while(a!=0){
		m=0;
		mm=0;
		scanf("%d",&b);
		for(i=0;i<=b;i++){
			for(j=0;j<=a;j++){
				c[i][j]=-1;
				d[i]=0;
				e[i]=0;
			}
		}
		for(i=0;i<b;i++){
				scanf("%d,%d",&d[i],&e[i]);
		}
		c[0][0]=0;
		for(i=0;i<=b;i++){
			for(j=0;j<=a;j++){
				if(c[i][j]>=0 && c[i][j]+d[i]>c[i+1][j+e[i]] && j+e[i]<=a && i+1<=b){
					c[i+1][j+e[i]]=c[i][j]+d[i];
				}
				if(c[i][j]>=0 && c[i+1][j]<c[i][j]&& i+1<=b){
					c[i+1][j]=c[i][j];
				}
			}
			
		}
		for(j=0;j<=a;j++){
			if(c[b][j]>m){
				m=c[b][j];
				mm=j;
				//printf("c=%d j=%d\n",c[b][j],j);
			}
		}
		/*for(i=0;i<=b;i++){
			for(j=0;j<=a;j++){
				printf("%4d",c[i][j]);
			}
			printf("\n");
		}
		printf("%d\n",c[b][49]);*/
		printf("Case %d:\n%d\n%d\n",g,m,mm);
		g++;
		scanf("%d",&a);
	}	
	return 0;
}

C++: #include <bits/stdc++.h>
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
constexpr int INF = 1000000000;
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
using namespace std;

using Weight = int;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(const int s = 0, const int d = 0, const Weight w = 0) : src(s), dst(d), weight(w) {}
};

using Edges = std::vector<Edge>;

class Graph {
  std::vector<Edges> g;

public:
  Graph(const int size = 0) : g(size) {}
  size_t size() const { return g.size(); }
  const Edges &operator[](const int i) const { return g[i]; }
  void addArc(const int src, const int dst, const Weight w = 1) { g[src].emplace_back(src, dst, w); }
  void addEdge(const int node1, const int node2, const Weight w = 1) {
    addArc(node1, node2, w);
    addArc(node2, node1, w);
  }
};

vector<Weight> dijkstra(const Graph &g, const int src) {
  using state = pair<Weight, int>;
  priority_queue<state, vector<state>, greater<state>> q;
  vector<Weight> dist(g.size(), INF);
  dist[src] = 0;
  q.emplace(0, src);
  while (q.size()) {
    Weight d;
    int v;
    tie(d, v) = q.top();
    q.pop();
    if (dist[v] < d) continue;
    for (auto &e : g[v]) {
      if (cmin(dist[e.dst], dist[v] + e.weight)) q.emplace(dist[e.dst], e.dst);
    }
  }
  return dist;
}

int main() {
  int caseIndex = 0;
  int W;
  while (cin >> W, W) {
    cout << "Case " << ++caseIndex << ':' << endl;
    int N;
    cin >> N;
    Graph g((N + 1) * (W + 1));
    rep(i, W) g.addArc(i, i + 1, 0);
    rep(i, N) {
      int v, w;
      char gomi;
      cin >> v >> gomi >> w;
      rep(j, W + 1) {
        g.addArc(i * (W + 1) + j, (i + 1) * (W + 1) + j, 0);
        if (j + w <= W) g.addArc(i * (W + 1) + j, (i + 1) * (W + 1) + j + w, -v);
      }
    }
    vector<Weight> dist;
    if (N * W >= 1e5)
      dist.assign(g.size(), 0);
    else
      dist = dijkstra(g, 0);
    // vector<Weight> dist = dijkstra(g, 0);
    int maxi = dist.back();
    cout << -maxi << endl;
    rep(i, W + 1) if (maxi == dist[N * (W + 1) + i]) {
      cout << i << endl;
      break;
    }
  }
}

C++: #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAX_N 1000
#define MAX_W 1000

int main(void){
  int W, N, cnt = 0;
  while(cin >> W && W && cin >> N){
    cnt++;
    int dp[MAX_W+1][MAX_N+1] = {0};
    for(int i = 0; i < N; i++){
      int v, w;
      scanf("%d,%d", &v, &w);
      for(int j = 0; j < W+1; j++){
        dp[j][i+1] = max(dp[j][i], (j-w >= 0 ? dp[j-w][i] + v : 0));
      }
    }
    cout << "Case " << cnt << ":" << endl;
    for(int j = 0; j < W + 1; j++){
      if(dp[j][N] == dp[W][N]){
        cout << dp[j][N] << endl << j << endl;
        break;
      }
    }
  }
  return 0;
}

C++: #include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<iomanip>
#include<set>
#include<numeric>
#include<sstream>
#include<random>
#include<cassert>
#include<climits>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
const int inf = 1e9 + 7;
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
#define ceil(a, b) a / b + !!(a % b)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)

const int limit = 2000;
int main() {
    int w;
    int c = 0;
    while (cin >> w && w) {
        c++;
        int n; cin >> n;
        int dp[limit] = {0};
        rep(i, n) {
            int v, ww; char ch;
            cin >> v >> ch >> ww;
            for (int i = 1000; i >= 0; --i) {
                if (dp[i]) chmax(dp[i + ww], dp[i] + v);
            }
            chmax(dp[ww], v);
        }
        int key = 0;
        rep(i, w + 1) if (dp[key] < dp[i]) key = i;
        cout << "Case " << c << ":" << endl;
        cout << dp[key] << endl << key << endl;
    }
    
}