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 loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
constexpr int INF = 1000000000;
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
using namespace std;

using Weight = int;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(const int s = 0, const int d = 0, const Weight w = 0) : src(s), dst(d), weight(w) {}
};

using Edges = std::vector<Edge>;

class Graph {
  std::vector<Edges> g;

public:
  Graph(const int size = 0) : g(size) {}
  size_t size() const { return g.size(); }
  const Edges &operator[](const int i) const { return g[i]; }
  void addArc(const int src, const int dst, const Weight w = 1) { g[src].emplace_back(src, dst, w); }
  void addEdge(const int node1, const int node2, const Weight w = 1) {
    addArc(node1, node2, w);
    addArc(node2, node1, w);
  }
};

vector<Weight> dijkstra(const Graph &g, const int src) {
  using state = pair<Weight, int>;
  priority_queue<state, vector<state>, greater<state>> q;
  vector<Weight> dist(g.size(), INF);
  dist[src] = 0;
  q.emplace(0, src);
  while (q.size()) {
    Weight d;
    int v;
    tie(d, v) = q.top();
    q.pop();
    if (dist[v] < d) continue;
    for (auto &e : g[v]) {
      if (cmin(dist[e.dst], dist[v] + e.weight)) q.emplace(dist[e.dst], e.dst);
    }
  }
  return dist;
}

int main() {
  int caseNum = 0;
  int W;
  while (cin >> W, W) {
    cout << "Case " << ++caseNum << ':' << endl;
    int N;
    cin >> N;
    Graph g((N + 1) * (W + 1));
    rep(i, W) g.addArc(i, i + 1);
    rep(i, N) {
      int v, w;
      char gomi;
      cin >> v >> gomi >> w;
      rep(j, W + 1) {
        g.addArc(i * (W + 1) + j, (i + 1) * (W + 1) + j, 0);
        if (j + w <= W) g.addArc(i * (W + 1) + j, (i + 1) * (W + 1) + j + w, -v);
      }
    }
    vector<Weight> dist = dijkstra(g, 0);
    int maxi = dist.back();
    cout << -maxi << endl;
    rep(i, W + 1) if (maxi == dist[N * (W + 1) + i]) {
      cout << i << endl;
      break;
    }
  }
}

C++: #include<stdio.h>
int i,j,l;
int w;
int n;
int kati,omosa;
int casecnt=0;
int maxkati,maxomosa;
long long int dp[1010][1010];//dp[お宝の総数][お宝の重さ]
int main(void){
	scanf("%d",&w);
	while(w!=0){
		for(i=0;i<=1000;i++){
			for(j=0;j<=1000;j++){
				if(j>0){
					dp[i][j]=-1;
				}
				else {
					dp[i][j]=0;
				}
			}
		}
		scanf("%d",&n);
		for(i=0;i<n;i++){
			scanf("%d,%d",&kati,&omosa);
			for(j=0;j<=w;j++){
				if(dp[i][j]>=0){
					if(dp[i+1][j+omosa]<kati){
						dp[i+1][j+omosa]=dp[i][j]+kati;
					}
				}
			}
			for(j=0;j<=w;j++){
				if(dp[i+1][j]<dp[i][j]){
					dp[i+1][j]=dp[i][j];
				}
			}
		}
		/*for(i=0;i<=n;i++){
			for(j=0;j<=w;j++){
				printf("%d ",dp[i][j]);
			}
			printf("\n");
		}*/
		maxomosa=0;
		maxkati=0;
		for(j=0;j<=w;j++){
			if(maxkati<dp[n][j]){
				maxkati=dp[n][j];
				maxomosa=j;
			}
		}
		casecnt++;
		printf("case %d:\n",casecnt);
		printf("%d\n",maxkati);
		printf("%d\n",maxomosa);
		scanf("%d",&w);
	}
	return 0;
}

C++: #include <iostream>
#include <array>
#include <string>
#include <tuple>
#include <vector>
#include<stdio.h>
#include<string.h>
using namespace std;
//using ll = long long;
#define out(s) cout << (s) << endl;

int dp[1010][1010];

int main()
{
	int W, N;
	cin >> W;
	vector<tuple<int, int>> anss;
	int cnt = 1;
	while (W!=0)
	{
		cin >> N;
		memset(dp, -1, sizeof(dp));
		dp[0][0] = 0;
		for (size_t i = 0; i < N; i++)
		{
			int vi, wi;
			scanf("%d,%d", &vi, &wi);
			for (size_t n = 0; n <= W; n++)
			{
				if (dp[i][n] != -1) {
					dp[i + 1][n] = max(dp[i][n], dp[i + 1][n]);
					if (n + wi > W)continue;
					dp[i + 1][n + wi] = max(dp[i][n] + vi, dp[i][n]);
				}
			}
		}
		int dp_max = *max_element(dp[N], dp[N] + W + 1);
		int index = 0;
		for (size_t i = 0; i < W+1; i++)
		{
			if (dp_max == dp[N][i]) { index = i; break; }
		}
		cout << "Case " << cnt << ":" << endl;
		cout << dp_max << endl;
		cout << index << endl;
		cin >> W;
		cnt++;
	}

	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;


long dp[1002][1001];
long 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];
		long res1=-1,res2=0;
		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,(long)j+w[i]);
					}
				}
			}
		}
		cout<<"Case "<<cnt<<":"<<endl;
		cout<<res1<<endl;
		cout<<res2<<endl;
	}
	return 0;
}
/*

*/