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
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <complex>
#include <math.h>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<long, long> PLL;
typedef long long LL;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(long i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

const long double EPS = 1e-12;
const LL INF = 1e18;


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


int main(){
	int maxw,N;
	int cnt=1;
	while(cin>>maxw){
		if(maxw==0)break;
		cin>>N;
		CLR(dp);
		char c;
		REP(i,N)cin>>v[i]>>c>>w[i];
		int res1=0,res2=10000;
		REP(i,N+1){
			REP(j,maxw+1){
				if(j+w[i]<=maxw){
					dp[i+1][j+w[i]]=max(dp[i+1][j+w[i]],dp[i][j]+v[i]);
					if(dp[i+1][j+w[i]]>res1){
						res1=dp[i+1][j+w[i]];
						res2=j+w[i];
					}else if(dp[i+1][j+w[i]]==res1){
						res2=min(res2,(int)j+w[i]);
					}
				}
			}
		}
		cout<<"Case "<<cnt<<":"<<endl;
		cout<<res1<<endl;
		cout<<res2<<endl;
	}
	return 0;
}
/*

*/

C++: #include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

int dk[10001][1001];

int main(){
	int i,j,takara[1001][2],w,n,c,maxv;
	c=0;
	while(0<=scanf("%d",&w)){
		if(w==0)break;
		scanf("%d",&n);
		++c;
		
		for(i=1;i<=n;i++){
			scanf("%d,%d",&takara[i][0],&takara[i][1]);
		}
		
		memset(dk,0,sizeof(dk));
		
		for(i=1;i<=n;i++){
			for(j=1;j<=w;j++){
				if(j>=takara[i][1]){
					dk[i][j]=(dk[i-1][j-takara[i][1]]+takara[i][0]>dk[i-1][j] ? dk[i-1][j-takara[i][1]]+takara[i][0]:dk[i-1][j]);
					continue;
				}
				dk[i][j]=dk[i-1][j];
			}
		}
		
		maxv=dk[n][w];
		
		for(i=0;i<=w;i++){
			if(maxv==dk[n][i])break;
		}
		
		printf("Case %d:\n",c);
		printf("%d\n%d\n",maxv,i);
	}
	return 0;
}

C++: #include "math.h"
#include "stdio.h"
#include <algorithm>
#include <string>
#include <vector>
#include <iostream>

using namespace std;


/** Problem0042 : A Thief
 Time Limit Exceeded **/

#define MAX_N 1100
#define MAX_W 1100

int W, N, tre[1100][2]={0}, solW, solN;
int dp[MAX_N][MAX_W];

pair<int, int> solve(int i, int j)
{
	if (dp[i][j] >= 0)
		return pair<int, int>(dp[i][j], j);
	
	pair<int, int> res;
	if (i == N) {
		res = pair<int, int>(0, W-j);
	} else if (j < tre[i][1]) {
		res = solve(i+1, j);
	} else {
		//res.first = max(solve(i+1, j).first, solve(i+1, j-tre[i][1]).first+tre[i][0]);
		
		if (solve(i+1, j).first > solve(i+1, j-tre[i][1]).first+tre[i][0]) {
			res = solve(i+1, j);
		} else if (solve(i+1, j).first < solve(i+1, j-tre[i][1]).first+tre[i][0]) {
			res = pair<int, int>(solve(i+1, j-tre[i][1]).first+tre[i][0], solve(i+1, j-tre[i][1]).second);
		} else {
			res = pair<int, int>(solve(i+1, j).first, min(solve(i+1, j).second, solve(i+1, j-tre[i][1]).second));
		}
	}
	return res;
}

int main()
{
	int set=0; char cam;
	while (1) {
		set++;
		
		cin >> W;
		solW = 0; solN = 0;
		if (W==0) break;
		cin >> N;
		
		memset(dp, -1, sizeof(dp));
		
		for (int i=0; i<N; i++) {
			cin >> tre[i][0] >> cam >> tre[i][1];
		}
		
		pair<int, int> sol = solve(0, W);
		
		cout << "Case " << set << ":" << endl;
		cout << sol.first << endl;
		cout << sol.second << endl;
	}
	return 0;
}

C++: #include<iostream>
#include<stdio.h>
using namespace std;
int dp[1001][1001];
int main(){
  int W,N,v[1000],w[1000];
  int n=1;
  int lastj;
  char jyama;
  while(cin>>W&&W){
    cin>>N;
    for(int i=0;i<N;i++){
      scanf("%d,%d",&v[i],&w[i]);
    }
    for(int i=0;i<N-1;i++){
      for(int j=0;j<=W;j++){
	if(j<w[i]){
	  dp[i+1][j]=dp[i][j];
	}else{
	  dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
	  if(dp[i+1][j]!=dp[i][j]) lastj=j;
	}
      }
    }
    cout<<"Case "<<n<<":"<<endl;
    cout<<dp[N-1][W]<<endl;
    cout<<lastj<<endl;
    ++n;
  }
}

C++: #include <stdio.h>

int dp[1024][10010];

int main(void)
{
	int i, j;
	int n;
	int wei;
	int w[1024];
	int k[1024];
	int b;
	int max;
	int mw;
	
	b = 0;
	while (scanf("%d", &wei), wei != 0){
		scanf("%d", &n);
		for (i = 0; i <= n; i++){
			if (i < n){
				scanf("%d,%d", &k[i], &w[i]);
			}
			for (j = 0; j < 10000; j++){
				dp[i][j] = 0;
			}
		}
		for (i = 0; i < n; i++){
			for (j = 0; j <= wei; j++){
				if (dp[i + 1][j + w[i]] < dp[i][j] + k[i] && j + w[i] <= wei){
					dp[i + 1][j + w[i]] = dp[i][j] + k[i];
				}
				if (dp[i + 1][j] < dp[i][j]){
					dp[i + 1][j] = dp[i][j];
				}
			}
		}
		max = 0;
		for (i = 0; i <= wei; i++){
			if (max < dp[n][i]){
				max = dp[n][i];
				mw = i;
			}
		}
		b++;
		printf("Case %d:\n", b);
		printf("%d\n%d\n", max, mw);
	}
	return (0);
}

C++: #include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
int main() {
	int w,n,c=1;
	while (scanf("%d",&w)) {
		if (w==0) break;
		scanf("%d",&n);
		int W[n],V[n];
		for (int i=0; i<n; i++) scanf("%d%*c%d",&V[i],&W[i]);
		int dp[n+1][w+1];
		int rw=1001,rv=0;
		for (int i=0; i<=w; i++) dp[n][i]=0;
		for (int i=n-1; i>=0; i--) {
			for (int j=0; j<=w; j++) {
				if (W[i]>j) dp[i][j]=dp[i+1][j];
				else {
					int r1=dp[i+1][j],r2=dp[i+1][j-W[i]]+V[i];
					if (r2>=r1) {
						if (rv<r2) {
							rv=r2;
							rw=j;
						} else if (rv==r2) {
							rw=min(rw,j);
						}
						dp[i][j]=r2;
					} else {
						dp[i][j]=r1;
					}
				}
			}
		}
		printf("Case %d:\n%d\n%d\n",c++,rv,rw);
	}
}