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>

#define SIZE 300005
#define MOD 1000000007LL
#define INF 1 << 30
#define LLINF 1LL << 60
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define DOWN(i,b,a) for(int i=b;i>=a;i--)
#define SET(a,c) memset(a,c,sizeof a)
#define FORALL(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define FOREACH(i,c) for(auto (i) : (c))
#define BIT(i,j) ((i)>>(j))&1
#define ALL(o) (o).begin(), (o).end()
#define ERASE(o) (o).erase(unique((o).begin(),(o).end()), (o).end())
#define SQ(x) ((x)*(x))
using namespace std;
typedef long long ll;
typedef valarray<int> Array;
typedef pair<ll,ll> Pll;
typedef pair<int, int> Pii;
typedef pair<double, double> Pdd;
template<typename T> inline void priv(vector<T>a){REP(i,a.size()){cout<<a[i];if(i==a.size()-1)cout<<endl;else cout<<" ";}}
int gcd(int a,int b){int c=max(a,b);int d=min(a,b);return c==0||d==0?c:gcd(c%d,d);}
int lcm(int a,int b){return a==0||b==0?0:a*b/gcd(a,b);}

int W, N;
int v[1010];
int w[1010];
const int NMAX = 1000;
const int VMAX = 10000;
int dp[NMAX*VMAX+10];

void solve1()
{
  int n1 = N/2;
  int n2 = (N + 1)/2;
  vector<pair<int,int> > a;
  REP(i,1<<n1)
  {
    int sw = 0, sv = 0;
    REP(j,n1) if(i & 1 << j)
    {
      sw += w[j];
      sv += v[j];
    }
    a.emplace_back(sw,sv);
  }
  sort(a.begin(),a.end());
  int m = 0;
  // for(auto x : a) printf("%d %d\n",x.first, x.second);
  // FOR(i,1,(1<<n1)-1)
  //   if(a[m].second < a[i].second) a[m++] = a[i];
  // for(auto x : a) printf("%d %d\n",x.first, x.second);
  int ans1 = 0, ans2 = 0;
  REP(i,1<<n2)
  {
    int sw = 0, sv = 0;
    REP(j, n2) if (i & 1 << j)
    {
      sw += w[j+n1];
      sv += v[j+n1];
    }
    if(sw <= W)
    {
      auto tmp = (lower_bound(a.begin(),a.end(),make_pair(W-sw, INF))-1);
      int tw = tmp->first;
      int tv = tmp->second;
      if(ans1 < sv+tv)
      {
        ans1 = sv + tv;
        ans2 = sw + tw;
      }
      else if(ans1 == sv+tv)
      {
        ans2 = min(ans2,sw+tw);
      }
    }
  }
  printf("%d\n%d\n",ans1,ans2);
}

void solve2()
{
  int NV = N*10000;
  fill_n(dp,NV+1,INF);
  dp[0] = 0;
  REP(i,N) DOWN(j,NV,v[i])
    dp[j] = min(dp[j],dp[j-v[i]]+w[i]);
  DOWN(i,NV,0) if(dp[i] <= W)
  {
    printf("%d\n%d\n",i,dp[i]);
    return;
  }
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  for(int c = 1; scanf("%d",&W), W; c++)
  {
    scanf("%d",&N);
    REP(i,N) scanf("%d,%d",&v[i],&w[i]);
    printf("Case %d:\n",c);
    if(N <= 30) solve1();
    else solve2();
  }
  return 0;
}

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[1002][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){
			REP(j,maxw){
				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++: //57
#include<iostream>
#include<algorithm>

using namespace std;

int main(){
  int c=0;
  for(int W;cin>>W,W;){
    c++;
    int N;
    cin>>N;
    int val[1001]={};
    while(N--){
      int v,w;
      (cin>>v).ignore()>>w;
      for(int i=1000;i-w>=0;i--){
	val[i]=max(val[i],val[i-w]+v);
      }
    }
    int i;
    for(i=W;i&&val[i]==val[i-1];i--) ;
    cout<<"Case "<<c<<':'<<endl;
    cout<<val[i]<<endl;
    cout<<i<<endl;
  }
  return 0;
}