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>
using namespace std;
vector<int> wmax;
int vmax;int n;
void dfs(vector<pair<int,int> > pii,int depth,int v,int w){
 
  if(w>n){
    return;
  }else if(v==vmax){wmax.push_back(w);
  }else if(v>vmax){wmax.clear();wmax.push_back(w);vmax=v;}
  if(pii.size()==depth+1)
    return;
  //cout<<pii[depth].first<<" "<<pii[depth].second<<endl;
  dfs(pii,depth+1,v+pii[depth].first,w+pii[depth].second);
  dfs(pii,depth+1,v,w);
  
}
int main(){
  int dataset=1;
  while(cin>>n,n){
    wmax.clear();vmax=0;
    int num;cin>>num;
    vector<pair<int,int> > pii;
    for(int i=0;i<num;i++){
      int a,b;
      scanf("%d,%d",&a,&b);
      if(b<n){
	pii.push_back(make_pair(a,b));
	//cout<<pii[pii.size()-1].first<<" "<<pii[pii.size()-1].second<<endl;
      }
    }
    pii.push_back(make_pair(0,0));
    dfs(pii,0,0,0);
    int minw=1000000000;
    //cout<<wmax.size()<<endl;
    for(int i=0;i<wmax.size();i++){
      cout<<wmax[i]<<endl;
      if(minw>wmax[i])
	minw=wmax[i];
    }
    cout<<"Case "<<dataset<<":"<<endl;
    cout<<vmax<<endl;
    cout<<minw<<endl;
    dataset++;
  }
  return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
#define all(vec) vec.begin(),vec.end()
typedef long long int ll;
typedef pair<int,int> P;
const ll MOD=1234567;
const ll INF=1000000010;
const ll LINF=1000000000000000010LL;
const int MAX=10000010;
const double EPS=1e-3;
int dx[4]={0,1,0,1};
int dy[4]={0,0,1,1};
int dp[1010][1010];
int main(){
	int W;
	int c=1;
	while(cin>>W,W){
		int n;cin>>n;
		int v[1010],w[1010];
		memset(dp,0,sizeof(dp));
		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+1][j]=max(dp[i+1][j],dp[i][j]);
				if(j+w[i]<=W){
					dp[i+1][j+w[i]]=max(dp[i+1][j+w[i]],dp[i][j]+v[i]);
				}
			}
		}
		int ans=0;
		int m=0;
		for(int i=0;i<=W;i++){
			if(ans<dp[n][i]){
				ans=dp[n][i];
				m=i;
			}
		}
		cout<<"Case "<<c<<":"<<endl;
		cout<<ans<<endl;
		cout<<m<<endl;
		c++;
	}
}

C++: #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int dp[1500][1500];
int main()
{
	int count=1,i,j,W,n;
	while(1)
	{
		cin >> W;
		if(W==0)return 0;
		scanf("%d",&n);
		memset(dp,0,sizeof(dp));
		int v[n],w[n];
		for(i=0;i<n;i++)
		{
			scanf("%d,%d",&v[i],&w[i]);
		}
		for(i=0;i<n;i++)
		{
			for(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(i=W;i>=0;i--)
		{
			if(dp[n][W]!=dp[n][i])break;
		}
		cout << "Case " << count << ':' << endl;
		cout << dp[n-1][W] << endl;
		cout << i+1 << endl;
		count++;
	}
	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int v[1000];
int w[1000];

int dp[1010][1010];

int main() {
	int W, N;
	int cnt = 1;
	while(scanf("%d", &W), W) {
		scanf("%d", &N);
		for(int i = 0; i < N; i++) {
			scanf("%d,%d", v + i, w + i);
		}

		fill((int*)begin(dp), (int*)end(dp), 0);
		for(int i = 0; i < N; i++) {
			for(int j = 0; j <= W; j++) {
				dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
				if(j + w[i] > W) continue;
				dp[i + 1][j + w[i]] = max(dp[i + 1][j + w[i]], dp[i][j] + v[i]);
			}
		}

		printf("Case %d:\n", cnt);
		int max_v = *max_element(dp[N], dp[N] + W + 1);
		for(int j = 0; j <= W; j++) {
			if(dp[N][j] == max_v) {
				printf("%d\n%d\n", max_v, j);
				break;
			}
		}
		cnt++;
	}
}

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

int sum[100+1];
int temp[100+1];
int size;

void update(int score, int weight) {
	for (int i = weight; i <= size; i++) {
		int a = sum[i-weight] + score;
		temp[i] = a > sum[i] ? a : sum[i];
	}
	for (int i = weight; i <= size; i++)
		sum[i] = temp[i];
}

int main() {
	int k = 0, n;
	while (cin >> size, size) {
		k++;
		cin >> n;
		for (int i = 0; i <= size; i++)
			sum[i] = temp[i] = 0;
		
		for (int i = 0; i < n; i++) {
			int a, b; scanf("%d,%d", &a, &b);
			update(a, b);
		}

		int w = size;
		while (w > 0 && sum[w-1] == sum[size]) w--;
		cout << "Case " << k << ":" << endl;
		cout << sum[size] << endl;
		cout << w << endl;
	}
	return 0;
}

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

const int MAX_W = 1024;
int dp[MAX_W];

int main()
{
  for (int tno = 1;; ++tno) {
      int W, N; scanf("%d%d", &W, &N);
      if (W == 0) break;

      memset(dp, 0, sizeof(dp));
      while (N--) {
          int w, v; scanf("%d, %d", &v, &w);
          for (int i = W; i - w >= 0; i--) {
              dp[i] = max(dp[i], dp[i - w] + v);
          }
      }
      int ans = 0;
      for (int i = 0; i <= W; i++) {
          if (dp[ans] < dp[i])
              ans = i;
      }
      printf("Case %d:\n", tno);
      printf("%d\n%d\n", dp[ans], ans);

  }
}

C++: #include <iostream>
#include <array>
#include <string>
#include <tuple>
#include <vector>
#include<stdio.h>
#include<string.h>
using namespace std;
//using ll = long long;
#define out(s) cout << (s) << endl;

int dp[1001][1001];

int main()
{
	int W, N;
	cin >> W;
	vector<tuple<int, int>> anss;
	while (W!=0)
	{
		cin >> N;
		memset(dp, -1, sizeof(dp));
		dp[0][0] = 0;
		for (size_t i = 0; i < N; i++)
		{
			int vi, wi;
			scanf("%d,%d", &vi, &wi);
			for (size_t n = 0; n <= W; n++)
			{
				if (dp[i][n] != -1) {
					dp[i + 1][n] = max(dp[i][n], dp[i + 1][n]);
					dp[i + 1][n + wi] = max(dp[i][n] + vi, dp[i][n]);
				}
			}
		}
		int dp_max = dp[N][W];
		int index = W;
		for (size_t i = W; i > 0; i--)
		{
			if (dp_max == dp[N][i])index = i;
		}
		anss.push_back(tuple<int, int>(index, dp_max));
		cin >> W;
	}
	int cnt = 1;
	for (auto item : anss) {
		int index, max;
		tie(index, max) = item;
		cout << "Case " << cnt << ":" << endl << max << endl << index << endl;
		cnt++;
	}
	return 0;
}

C++: #include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int tr[1100][2]={0},dp[1100][1100]={0};
int main(){
  for(int c=1;;c++){
    int w,n,ans = 0,q;
    cin >>w;
    if(w == 0) break;
    cin >>n;
    for(int i=0; i<1100; i++){
      tr[i][0] = tr[i][1] = 0;
      for(int j=0; j<1100; j++) dp[i][j] = 0;
    }
    for(int i=1; i<=n; i++) scanf("%d,%d",&tr[i][0],&tr[i][1]);
    for(int i=1; i<=n; i++){
      for(int j=0; j<=w; j++){
	if(j == 0) dp[i][tr[i][1]] = max(dp[i][tr[i][1]],tr[i][0]);
	if(dp[i-1][j]!=0){
	  if(j+tr[i][1]<=w) dp[i][j+tr[i][1]] = max(dp[i][j+tr[i][1]],dp[i-1][j]+tr[i][0]);
	  dp[i][j] = max(dp[i][j],dp[i-1][j]);
	}
      }
    }
    for(int i=0; i<=w; i++){
      if(ans<dp[n][i]){
	ans = dp[n][i];
	q = i;
      }
    }
    cout <<"Case "<<c<<":"<<endl<<ans<<endl<<q<<endl;
  }
  return 0;
}