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<stdio.h>
#include<algorithm>
using namespace std;
int c[1000],d[1000];
int dp[1001][1001];
int main(){
	int a,b;
	int now=0;
	while(scanf("%d",&a),a){
		scanf("%d",&b);
		for(int i=0;i<b;i++){
			scanf("%d,%d",c+i,d+i);
		}
		for(int i=0;i<=b;i++)
			for(int j=0;j<=a;j++)
				dp[i][j]=-99999999;
		for(int i=0;i<=a;i++)dp[0][i]=0;
		for(int i=1;i<=b;i++){
			for(int j=0;j<=a;j++){
				if(j>=d[i-1])dp[i][j]=max(dp[i-1][j],dp[i-1][j-d[i-1]]+c[i-1]);
				else dp[i][j]=dp[i-1][j];
			}
		}
		int weight=0;
		int ans=0;
		for(int i=0;i<=a;i++){
			if(weight<dp[b][i]){
				weight=dp[b][i];
				ans=i;
			}
		}
		printf("Case %d:\n%d\n%d\n",++now,weight,ans);
	}
}

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

int W,N,value[1000],weight[1000],cost;
int dp[1001][1001],data=0,w;
int main(){

  while(cin >>W){
    if(W==0)break;
    cin >>N;
    for(int i=0;i<=N;i++){
      for(int j=0;j<=W;j++){
	dp[i][j]=0;
      }
    }
    data++;
    for(int i=0;i<N;i++) scanf("%d,%d",&value[i],&weight[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+weight[i]<=W)
	dp[i+1][j+weight[i]] = max(dp[i+1][j+weight[i]],dp[i][j]+value[i]);
      }
    }
    cost=dp[N][W];
    w=-1;
   
	for(int j=0;j<=W;j++){
	  if(dp[N][j] == cost){
	    w=j;
	    break;
	  }	  
	  //      cout <<weight[i]<<endl;
    }
      cout <<"Case "<<data<<":\n"<<cost<<endl<<w<<endl;
  }

  return 0;
}

C++: #include <iostream>
#include <stdio.h>
#include <math.h>

using namespace std;

int Max(int a,int b){
	if(a>=b)return a;
	else return b;
}

int main(){
	int n,w;

	int cnt = 1;

	while(true){
	cin>>w;
	if(w==0) break;
	cin>>n;
	int *dataW = new int[n];
	int *dataV = new int[n];
	int *ans = new int[w];
	char tmp;
	int num;
	int max = 0;
	int ansW;
	for(int i=0;i<n;i++){
		cin>>num;
		dataV[i] = num;
		cin>>tmp;
		cin>>num;
		dataW[i] = num;
	}
	for(int i=0;i<w;i++){
		ans[i] = -1;
	}
	ans[0] = 0;

	for(int i=0;i<n;i++){
		for(int j=w-1;j>=0;j--){
			if(ans[j] >= 0){
				int tmpW = j + dataW[i];
				if(tmpW < w){
					ans[tmpW] = Max(ans[tmpW],ans[j] + dataV[i]);
				}
			}
		}
		/*
		for(int j=0;j<w;j++) cout<<ans[j]<<" ";
		cout<<endl;
		*/
	}
	for(int i=0;i<w;i++){
		if(max<=ans[i]){
			max = ans[i];
			ansW = i;
		}
	}
	cout<<"Case "<<cnt<<":"<<endl<<max<<endl<<ansW<<endl;
	cnt++;
}
return 0;
}
/*
50
5
60,10
100,20
120,30
210,45
10,4
50
5
60,10
100,20
120,30
210,45
10,4
0
*/

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

struct Item{
	int v,w;
	int idx;	
};
const int INF = 1000000000;
class Knapsack{
public:
	
	
	int maximumWeight;
	vector<Item> items;
	Knapsack(int maximumWeight_,vector<Item> items_) : maximumWeight(maximumWeight_),items(items_) {
		used.resize(items.size(),false);
		totalWeight = totalValue = 0;
		sort(items.begin(),items.end(),[](Item a,Item b){ return a.v * b.w > b.v * a.w; });
	}
	int totalValue;
	int totalWeight;
	vector<bool> used;
	bool operator < (const Knapsack &op) const {
		if( totalValue == op.totalValue )
			return totalWeight > op.totalWeight;
		return totalValue < op.totalValue;
	}

	bool canPut(const Item &x){
		return !used[x.idx] && x.w <= maximumWeight - totalWeight;
	}
	bool putItem(const Item &x){
		if( canPut(x) ){
			totalWeight += x.w;
			totalValue += x.v;
			used[x.idx] = true;
			return true; // success
		}else{
			return false; // failure
		}
	}
	bool removeItem(const Item &x){
		if( used[x.idx] ){
			totalWeight -= x.w;
			totalValue -= x.v;
			used[x.idx] = false;
			return true;
		}
		return false;
	}
	int swapAtoB(Item x,Item y){
		if( used[x.idx] && !used[y.idx] ){
			if( totalWeight - x.w + y.w > maximumWeight ) return -INF;
			return y.v - x.v;
		}else{
			return -INF;
		}
	}
	Knapsack knapSackDP(int scale) const{
		Knapsack res = *this;
		int maximumValue = -INF;
		for( auto i : res.items ){
			maximumValue = max(maximumValue,i.v);
		}

		double rate = min(1.0,1.*scale/maximumValue);
		for( auto &i : res.items ){
			i.v = (int)(ceil(rate*i.v)+1e-9);
		}
		
		vector<int> dp(scale+1,INF),lastId(scale+1,-1);
		dp[0] = 0;
		for(int i = 0 ; i < res.items.size() ; i++){
			if( res.used[i] ) continue;
			for(int j = scale ; j >= res.items[i].v ; j--){
				if( dp[j-res.items[i].v] + res.items[i].w < dp[j] ){
					dp[j] = dp[j-res.items[i].v] + res.items[i].w;
					lastId[j] = i;
				}
			}
		}
		for(int i = scale ; i >= 0 ; i--){
			if( dp[i] <= maximumWeight - totalWeight ){
				int cur = i;
				while(cur > 0){
					int p = lastId[cur];
					res.putItem(res.items[p]);
					cur -= res.items[p].v;
					if( p == -1 ) exit(0);
				}
				break;
			}
		}
		return res;
	}
	Knapsack localImprovement() const{
		Knapsack res = *this;
		while(true){
			// ????¬??????????????????????????????§??????????
			for(int i = 0 ; i < res.items.size() ; i++){	
				res.putItem(res.items[i]);
			}
			auto reflesh = [&](){
				for(int i = 0 ; i < res.items.size() ; i++){
					if( res.used[i] ){

						auto tmp = res;
						tmp.removeItem(tmp.items[i]);
						for(int j = 0 ; j < tmp.items.size() ; j++){
							if( i != j && !tmp.used[j] ){	
								tmp.putItem(tmp.items[j]);
							}
						}
						if( res < tmp ){
							res = tmp;
							return true;
						}
					}
				}
				return false;
			};
			if( reflesh() ) continue;
			
			auto reflesh2 = [&](){
				for(int i = 0 ; i < res.items.size() ; i++){
					if( res.used[i] ){

						for(int j = 0 ; j < res.items.size() ; j++){
							if( !res.used[j] ){
								if( res.swapAtoB(res.items[i],res.items[j]) >= 0 ){
									res.removeItem(res.items[i]);
									res.putItem(res.items[j]);
									return true;
								}
							}
						}
					}
				}
				return false;
			};
			if( reflesh2() ) continue;
			break;
		}
		return res;
	}
};




int main(){
	int n,m;
	int t=1;
	while(cin >> n >> m && n){
		vector<Item> items;
		for(int i = 0 ; i < m ; i++){
			int x,y;
			scanf("%d,%d",&x,&y);
			items.push_back({x,y,i});
		}
		Knapsack knap(n,items);
		knap = knap.knapSackDP(20000);
		cout << "Case " << t++ << ":" << endl;
		//knap = knap.localImprovement();
		cout << knap.totalValue << "\n" << knap.totalWeight << endl;
	}
}