Go: package main

import (
	"bufio"
	"os"
	"strconv"
	"strings"
	"fmt"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	Case := 1
	for {
		scanner.Scan()
		W, _ := strconv.Atoi(scanner.Text())
		if W == 0 {
			break
		}
		scanner.Scan()
		n, _ := strconv.Atoi(scanner.Text())
		w := make([]int, n+1)
		v := make([]int, n+1)
		for i := 1; i <= n; i++ {
			scanner.Scan()
			info := strings.Split(scanner.Text(), ",")
			v[i], _ = strconv.Atoi(info[0])
			w[i], _ = strconv.Atoi(info[1])
		}
		// fmt.Println(v)
		// fmt.Println(w)
		dp := make([][]int, n+1)
		for i := range dp {
			dp[i] = make([]int, W+1)
		}
		maxV := -(1 << 21)
		minW := 1 << 21
		for i := 1; i <= n; i++ {
			for j := 1; j <= W; j++ {
				// fmt.Println(dp)
				if j-w[i] >= 0 {
					dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])
					if maxV < dp[i][j] {
						maxV = dp[i][j]
						minW = j
					} else if maxV == dp[i][j] {
						minW = min(minW, j)
					}
				} else {
					dp[i][j] = dp[i-1][j]
				}
			}
		}
		fmt.Printf("Case %d:\n", Case)
		Case += 1
		fmt.Println(maxV)
		fmt.Println(minW)
	}
}
func max(x, y int) int {
	if x < y {
		return y
	}
	return x
}
func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

C++: #include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
 
const double EPS = 1e-10;
const ll INF = 100000000;
const ll MOD = 1000000007;

struct ITEM {
    int v, w;
    double x;

    bool operator>(const ITEM& right) const {
        return x > right.x;
    }
} item[1000];

int N, W;
int v[1000], w[1000];
int ans;
int ans2;

void dfs (int pos, int val, int sum, bool flag) {
    if (ans < val) {
        ans = val;
        ans2 = sum;
    }
    if (ans == val) {
        ans2 = min(ans2, sum);
    }
    if (pos == N) return;
    if (flag) {
        int _W = W-sum;
        double lim = val;
        for (int i = pos; i < N; i++) {
            if (_W >= item[i].w) {
                lim += item[i].v;
                _W -= item[i].w;
            } else {
                lim += _W * item[i].x;
                break;
            }
        }
        if (lim+EPS < ans) {
            return;
        }
    }
    if (sum+item[pos].w <= W) {
        dfs(pos+1, val+item[pos].v, sum+item[pos].w, false);
    }
    dfs(pos+1, val, sum, true);
}

int main() {
    int testcase = 1;
    while (cin >> W) {
        if (W == 0) break;
        ans = 0;
        cin >> N;
        rep(i,N) {
            char tmp;
            cin >> item[i].v >> tmp >> item[i].w;
            item[i].x = item[i].v / (double)item[i].w;
        }
        sort(item, item+N, greater<ITEM>());
        dfs(0, 0, 0, false);
        cout << "Case " << testcase << ":" << endl;
        cout << ans << endl;
        cout << ans2 << endl;
        testcase++;
    }
}

C++: #include<stdio.h>

int main()
{
	for(int c=1;;c++)
	{
		int w,n,kati[1000],weit[1000],weitk=0,katik=0;
		scanf("%d",&w);
		if(w==0)
		{
			return 0;
		}
		scanf("%d",&n);
		
		int katisum[100][100]={0},weitsum[100][100]={0};
		for(int x=0;x<n;x++)
		{
			scanf("%d,%d",&kati[x],&weit[x]);
		}
		for(int y=0;y<n;y++)
		{
			for(int z=y;z<n;z++)
			{
				for(int r=y;r<=z;r++)
				{
					katisum[y][z]+=kati[r];
					weitsum[y][z]+=weit[r];
				}
			}
		}

		for(int y=0;y<n;y++)
		{
			for(int z=0;z<n;z++)
			{
				if(w>=weitsum[y][z]&&katik<katisum[y][z])
				{
					weitk=weitsum[y][z];
					katik=katisum[y][z];
				}
				
			}
		}
		for(int y=0;y<n;y++)
		{
			for(int z=0;z<n;z++)
			{
				if(katik==katisum[y][z]&&weitk>weitsum[y][z])
				{
					weitk=weitsum[y][z];
				}
			}
		}
		printf("Case %d:\n%d\n%d\n",c,katik,weitk);
	}
}

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

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

int main(void){
	while(scanf("%d", &W)&&W){
		int ans;
		scanf("%d", &N);
		for(int i = 1; i <= N; i++){
			scanf("%d,%d", &p[i], &w[i]);
		}
		for(int i = 1; i <= N; i++){
			for(int j = 1;j <= W; j++){
				if(i-1 < 0 || j-w[i]<0)continue;
				dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+p[i]);
			}
		}
		c++;
		printf("Case%2d:\n",c);
		printf("%d\n",dp[N][W]);
		for(int i = 0; i < W; i++){
			if(dp[N][W] == dp[N][W-i]){
				ans = i;
			}
		}
		printf("%d\n",W-ans);
		/*ツ渉可甘コツ可サ*/
		for(int i = 0; i < 1001; i++){
			w[i] = 0;
			p[i] = 0;
		}
		for(int i = 0; i < 10001; i++){
			for(int j = 0; j < 1000; j++){
				dp[i][j] = 0;
			}
		}
	}
	return 0;
}

C++: #include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <algorithm>
#include <functional>

using namespace std;

#define rep(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define foreach(itr,c) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define MAX 1010

int W,N;
int w[MAX],v[MAX];
ll dp[MAX][MAX];

int main(){
  int i,j;

  for(;;){
    scanf("%d",&W); if(W == 0) break;
    scanf("%d",&N);
    rep(i,N) scanf("%d,%d",&v[i],&w[i]);

    rep(i,MAX) rep(j,MAX) dp[i][j] = 0;

    int res;
    for(i = 0; i <= N; i++){
      for(j = 0; j <= W; j++){
        if(j - w[i] < 0) dp[i+1][j] = dp[i][j];
        else {
          if(dp[i][j] < dp[i][j-w[i]] + v[i]){
            dp[i+1][j] = dp[i][j-w[i]] + v[i];
            res = j;
          }
          else dp[i+1][j] = dp[i][j];
        }
      }
    }

    printf("%d\n%d\n",dp[N][W],res);
  }

  return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <vector>
#include <string>
#include <cmath>
#include <map> 
using namespace std;
 
const int MAX= 10000100;

#define loop(i,a,b) for(int i = a ; i < b ; i ++)
#define rep(i,a) loop(i,0,a)
#define all(a) (a).begin(),(a).end()
#define MAX_V 1000
#define MAX_W 10000
int W,N;
int dp[MAX_V+1][MAX_W+1];
int w[MAX_W+1];
int v[MAX_V+1];
void solve(){
  int cnt = 0;
  vector<int> data(N,0);
  for(int i = N - 1 ; i >= 0 ; i --){
    
    for(int j = 0 ; j <= W ; j ++){
    data[i]++;
      if(j<w[i]){
	data[i]--;
	dp[i][j] = dp[i+1][j];
      }else {
	dp[i][j] = max(dp[i+1][j] , dp[i+1][j-w[i]] + v[i]);

	if(dp[i+1][j] < dp[i+1][j-w[i]] + v[i]){
	  data[i]--;
	}
      }
    }
  }
  rep(i,N){
    if(data[i]==0){
      cnt+= w[i];
    }
  }
  printf("%d\n",dp[0][W]);
  cout<<cnt<<endl;
}

int main(void){
  int cnt = 0;
  while(cin>>W,W){
    cout<<"Case "<<++cnt<<":"<<endl;
    cin>>N;
    for(int i = 0 ; i < N ; i ++){
      scanf("%d,%d",&v[i],&w[i]);
    }
    solve();
    
  }
  
}

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));
        
        REP(n)rep(j, wl+1 - w[i])
            dp[i+1][j + w[i]] = max(dp[i][j + w[i]], dp[i][j] + v[i]);
        
        int answ = 0, ansv = -1;
        for(int i = wl;i!=0;i--)if(ansv <= dp[n][i]){ ansv = dp[n][i]; answ = i;}
        cout << "Case " << casen << ":\n" << ansv << "\n" << answ << endl;
        casen++;
    }

    return 0;
}