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<iostream>
#include<iomanip>
#include<queue>
#include<string>
#include<stack>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<utility>
#include<map>
#include<set>
#include<vector>
#include<functional>

using namespace std;

#ifdef DEBUG
#define dprintf      printf
#define dout(x)      cout<<#x" = "<<(x)<<endl
#define darray(x,n)    {int i;rep(i,n)cout<<#x"["<<i<<"] = "<<*((x)+i)<<endl;}
#define dloop(i,s,g) for((i)=(s);(i)<(g);(i)++)
#define drep(i,n)    for((i)=0;(i)<(n);(i)++)
#define dstop()      scanf("%*c")
#else
#define dprintf      (1)?0:printf
#define dout(x)
#define darray(x,n)
#define dloop(i,s,g) if(1){}else
#define drep(i,n)    if(1){}else
#define dstop()      if(1){}else
#endif

#define F    first
#define S    second
#define pb   push_back
#define mp   make_pair

#define loop(i,s,g) for((i)=(s);(i)<(g);(i)++)
#define rep(i,n)    for((i)=0;(i)<(n);(i)++)
#define all(x)      (x.begin(),x.end())
#define in(T,...) T __VA_ARGS__; impl(__VA_ARGS__);
#define array(T,id,n) T id[n]; rep(i,n)cin>>id[i];

//#define int long long;
#ifndef int
#define INF  (0x7fffffff)
#else
#define LINF (0x7fffffffffffffff)
#endif

typedef  long long           ll;
typedef  unsigned            ui;
typedef  unsigned long long  ull;
typedef  pair<int,int>       i_i;
typedef  pair<ll,int>        ll_i;
typedef  pair<ll,ll>         ll_ll;
typedef  pair<double,int>    d_i;
typedef  pair<double,double> d_d;

void impl(){};
template <typename T,typename... TS >
void impl(T &head,TS &... tail)
{
  cin>>head;
  impl(tail ...);
}




int dp[1123];
int W,n;
int v[1123];
int w[1123];

signed main(void)
{
  int i,j,k=0;

  while(1)
    {
      k++;
      rep(i,1123)dp[i]=0;
      int a=0;
      cin>>W;
      if(!W)break;
      cin>>n;
      rep(i,n)
	scanf("%d%*c%d",&v[i],&w[i]);
      rep(i,n)
	for(j=W;j>=w[i];j--)
	  dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
      rep(i,W+1)
	if(dp[i]>dp[a])a=i;
      printf("Case %d:\n%d\n%d\n",k,dp[a],a);
    }
  return 0;
}

C++: // DP
#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAX_N 1001
#define MAX_W 1001
using namespace std;

int main(){
	int caseNum = 1;
	int ans;
	int W, n;
	int v[MAX_N];
	int w[MAX_N];
	int dp[MAX_N][MAX_W];
	while(cin >> W){
		if(W == 0){
			break;
		}
		cin >> n;
		for (int i = 0; i < n; i++) {
			scanf("%d,%d", &v[i], &w[i]);
		}
		
		memset(dp, 0, sizeof(dp));
		for (int i = 0; i < n; 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]);
				}
			}
		}
		// answer
		cout << "Case " << caseNum++ << ":" << endl;
		for (int i = W; i >= 0; i--) {
			if(dp[n][W] != dp[n][i]) {
				ans = i+1;
				break;
			}
		}
		cout << dp[n][W] << endl;
		cout << ans << endl;
	}
	return 0;
}

C++: #include <iostream>
#include <utility>
#include <vector>
#include <cstring>
using namespace std;
const int MAX_N = 1000,MAX_M = 1000;
int n;
typedef pair<int,int> P;
P ilist[MAX_N];
P memo[MAX_N + 1][MAX_M + 1];

P comp(const P &a,const P &b){
	if(a.first < b.first) return b;
	return a;
}

P dp(int now,int lim){
	if(memo[now][lim].first > -1){
		return memo[now][lim];
	}
	P res;
	if(now == n) return make_pair(0,0);
	else if(lim < ilist[now].second){
		res = dp(now + 1,lim);
	}
	else{
		res = dp(now + 1,lim - ilist[now].second);
		res.second += ilist[now].second;
		res.first += ilist[now].first;
		res = comp(dp(now + 1,lim),res);
	}
	return memo[now][lim] = res;
}

int main(){
	int lim,cnt = 0,w,v;
	P item;
	char buf;
	while(cin >> lim,lim){
		for(int i = 0;i <= MAX_N;++i){
			for(int j = 0;j <= MAX_M;++j){
				memo[i][j] = make_pair(-1,-1);
			}
		}
		++cnt;
		cin >> n;
		for(int i = 0;i < n;++i){
			cin >> v >> buf >> w;
			ilist[i] = make_pair(v,w);
		}
		item = dp(0,lim);
		cout << "Case " << cnt << ":" << endl;
		cout << item.first << endl << item.second << endl;
	}
	return 0;
}

C++: #include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;

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

int solve(int i, int j) {
	if (dp[i][j] != -1)return dp[i][j];

	int res;
	if (i == N)res = 0;
	else if (j < w[i])res = solve(i + 1, j);
	else {
		res = max(
			solve(i + 1, j),
			solve(i + 1, j - w[i]) + v[i]
		);
	}
	return dp[i][j] = res;
}

int main() {
	int now = 1;
	while (1) {
		cin >> W;
		if (W == 0)break;
		cin >> N;
		for (int i = 0; i < N; i++) {
			scanf_s("%d,%d", v + i, w + i);
		}

		for (int i = 0; i <= N; i++) {
			for (int j = 0; j <= W; j++) {
				dp[i][j] = -1;
			}
		}
		solve(0, W);
		for (int i = 0; i <= N; i++) {
			for (int j = 0; j <= W; j++) {
				cout << i << ":" << j<<"=" << dp[i][j] << endl;
			}
		}
		int value = -1; int weight;
		for (int i = 0; i <= W;i++) {
			if (value < dp[0][i]) {
				value = dp[0][i];
				weight = i;
			}
		}
		cout << "Case " << now++ << ":" << endl << value << endl << weight-1 << endl;
	}
}