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++
	}
}

Python: # coding: utf-8
# Here your code !
count = 1

while 1:
    W = int(input())
    if W == 0:
        break
    N = int(input())
    data =[]
    dp = [[[-1,0]for i in range(W+1)]for i in range(N+1)]
    for i in range(N):
        data.append(input().split(","))

    for i in range(W+1):
        dp[N][i][0] = 0
    for i in reversed(range(N)):
        for capa in range(W+1):
            if int(data[i][1]) >  capa:
                dp[i][capa][0] = dp[i+1][capa][0]
                dp[i][capa][1] = dp[i+1][capa][1]
            else:
                dp[i][capa][0] = max(int(data[i][0])+dp[i+1][capa-int(data[i][1])][0],dp[i+1][capa][0])
                dp[i][capa][1] = dp[i+1][capa][1]
                if dp[i][capa][0] != dp[i+1][capa][0]:
                    dp[i][capa][1] += int(data[i][1])
    print("Case " + str(count) +":")
    print(max(max(dp))[0])
    print(max(max(dp))[1])
    print(dp)
    count += 1

Python: c=0
for W in iter(input,'0'):
 c+=1
 W=int(W)
 dp=[0]*-~W
 for _ in[0]*int(input()):
  v,w=map(int,input().split(','))
  for i in range(W,w-1,-1):
   if dp[i]<dp[i-w]+v:dp[i]=dp[i-w]+v
 for i in range(W+1):
  if dp[W]==dp[i]:print(f'Case {c}:\n{dp[W]}\n{i}');break

Python: for i in range(1, 100):
    W = int(input())
    if not W:
        break
    N = int(input())
    data = [tuple(map(int, input().split(','))) for _ in range(N)]
    dp = [[[0, 0] for j in range(W + 1)] for i in range(N + 1)]
    print('Case {0}:'.format(i))
    for i in range(1, N + 1):
        for j in range(W + 1):
            if data[i - 1][1] <= j:
                pt = dp[i - 1][j - data[i - 1][1]][:]
                for k in range(2):
                    pt[k] += data[i - 1][k]
                dpt = dp[i - 1][j][:]
                if pt[0] > dpt[0]:
                    dp[i][j] = pt
                elif dpt[0] > pt[0]:
                    dp[i][j] = dpt
                else:
                    dp[i][j] = pt if pt[1] < dpt[1] else dpt
            else:
                dp[i][j] = dp[i - 1][j]
    for i in range(2):
        print(dp[N][W][i])

Python: c=0
for W in iter(input,'0\n'):
 c+=1
 W=int(W)
 dp=[0]*-~W
 for _ in[0]*int(input()):
  v,w=map(int,input().split(','))
  for i in range(W,w-1,-1):
   if dp[i]<dp[i-w]+v:dp[i]=dp[i-w]+v
 for i in range(W+1):
  if dp[W]==dp[i]:print(f'Case {c}:\n{dp[W]}\n{i}');break

Python: c=0
for W in iter(input,'0'):
 c+=1
 W=int(W)
 d=[0]*-~W
 for _ in[0]*int(input()):
  v,w=map(int,input().split(','))
  for i in range(W,w-1,-1):
   if d[i]<d[i-w]+v:d[i]=d[i-w]+v
 print(f'Case {c}:\n{d[W]}\n{d.index(d[W])}')

Python: case = 0
while True:
    case += 1
    w_max = int(input())
    if w_max == 0:
        break
    n = int(input())

    w = [0 for i in range(n)]
    v = [0 for i in range(n)]
    for i in range(n):
        a, b = map(int, input().split(","))
        v[i] = a
        w[i] = b

    dp = [[0 for j in range(w_max + 1)] for i in range(n + 1)]
    for i in range(n)[::-1]:
        for j in range(w_max + 1):
            if j < w[i]:
                dp[i][j] = dp[i + 1][j]
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i])
    print("Case ",case,":",sep="")
    print(max(dp[0]))
    print(dp[0].index(max(dp[0])))

Python: c=0
for W in iter(input,'0'):
 c+=1
 W=int(W)
 dp=[0]*-~W
 for _ in[0]*int(input()):
  v,w=map(int,input().split(','))
  for i in range(W,w-1,-1):
   if dp[i]<dp[i-w]+v:dp[i]=dp[i-w]+v
 print(f'Case {c}:\n{dp[W]}\n{dp.index(dp[W])}')

Python: c = 0
while True:
  W = int(input())
  if W == 0:
    break
  c += 1
  N = int(input())

  vl = [0]
  wl = [0]
  for i in range(N):
    [v,w] = list(map(int,input().split(",")))
    vl.append(v)
    wl.append(w)
  dp = [[0 for i in range(W+1)] for j in range(N+1)]
  for i in range(N+1):
    for j in range(W+1):
      if i == 0 or j == 0:
        dp[i][j] = 0
      else:
        if wl[i] <= j:
          dp[i][j] = max(dp[i-1][j-wl[i]] + vl[i], dp[i-1][j])
        else:
          dp[i][j] = dp[i-1][j]
  ls = dp[N].copy()
  ls.reverse()
  max_w = W
  for i in range(1,W+1):
    if ls[i] == dp[N][W]:
      max_w -= 1
    else:
      break

  print("Case "+str(c)+":")
  print(dp[N][W])
  print(max_w)

Python: 

def rec(i, j):
	#print("rec({}, {}) called".format(i, j))
	if i in dphash and j in dphash[i]:
		return dphash[i][j]
	if i == N:
		ans = (0, W - j)
	elif j < wl[i]:
		ans = rec(i + 1, j)
	else:
		(v1, w1) = rec(i + 1, j)
		(v2, w2) = rec(i + 1, j - wl[i])
		v2 += vl[i]
		if v1 > v2:
			ans = (v1, w1)
		elif v1 < v2:
			ans = (v2, w2)
		elif v1 == v2:
			if w1 < w2:
				ans = (v1, w1)
			else:
				ans = (v2, w2)
	#dp[i][j] = ans
	if i in dphash:
		dphash[i][j] = ans
	else:
		dphash[i] = {}
		dphash[i][j] = ans

	return ans

case = 1
while True:
	W = int(input())
	if W == 0: break
	N = int(input())
	vl = []
	wl = []
	for _ in range(N):
		v, w = map(int, input().split(','))
		vl.append(v)
		wl.append(w)
	#dp = [[-1 for j in range(2500)] for i in range(2500)]
	dphash = {}
	(v, w) = rec(0, W)

	print("Case {}:".format(case))
	print(v)
	print(w)
	case += 1

Python: #!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin
from itertools import count

def douteki(limit, data):
    V = [[0 for w in xrange(limit+1)] for i in xrange(len(data)+1)]
    W = [[0 for w in xrange(limit+1)] for i in xrange(len(data)+1)]
    for i in xrange(len(data)+1):
        for w in xrange(limit+1):
            diff = w - data[i-1][1]
            if i - 1 >= 0 and diff >= 0:
                v1 = V[i-1][diff] + data[i-1][0]
                w1 = W[i-1][diff] + data[i-1][1]
            else:
                v1 = 0
                w1 = 0
            v2 = V[i-1][w]
            w2 = W[i-1][w]

            V[i][w], W[i][w] = (v1, w1) if v1 >= v2 else (v2, w2)
    return V[-1][-1], W[-1][-1]

for case in count(1):
    W = int(stdin.readline())
    if not W:
        break

    N = int(stdin.readline())
    data = []
    for _ in xrange(N):
        data.append([int(s) for s in stdin.readline().split(',')])

    value, weight = douteki(W, data)
    print('Case {}:\n{}\n{}'.format(case, value, weight))