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: cnt = 0
while True:
    cnt += 1
    maxweight = int(input())
    if maxweight == 0:
        break
    length = int(input())
    tresure = []
    dp = [[0 for n in range(length+1)] for m in range(maxweight + 1)]
    answeight = 0
    ansvalue = 0
    for l in range(length):
        v,w = (int(n) for n in input().split(","))
        tresure.append([v,w])
    for outer in range(length + 1):
        if outer == 0:
            continue
        weight = tresure[outer-1][1]
        value = tresure[outer-1][0]
        dp[weight][outer] = max(dp[weight][outer],value)
        for inner in range(maxweight + 1):
            if dp[inner][outer - 1] != 0:
                beforevalue = dp[inner][outer - 1]
                beforeweight = inner
                dp[inner][outer]  = max(beforevalue,dp[inner][outer])
                if beforeweight + weight <= maxweight:
                    nowvalue = dp[beforeweight + weight][outer]
                    dp[beforeweight + weight][outer] = max(nowvalue,beforevalue+value)
    #print(dp)
    for a in range(maxweight+1):
        #print(dp[a][length])
        if ansvalue < dp[a][length]:
            ansvalue = dp[a][length]
            answeight = a
    print("Case {0}:".format(cnt))
    print(ansvalue)
    print(answeight)

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] = capa
               # 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: # ナップサック問題を python で解く
case = 0
while True:
    case += 1
    w = int(input())
    if w == 0:
        break
    n = int(input())
    item = []
    for i in range(n):
        item.append(tuple(map(int, input().split(","))))

    dp = [ [0 for j in range(w + 1)] for i in range(n + 1) ]
    for i in range(n):
        for j in range(w + 1):
            value  = item[i][0]
            weight = item[i][1]
            # dp[i][j] : 0..i番目の荷物、重さ j 以下の最大の価値
            if j - weight >= 0 and dp[i+1][j - weight] == dp[i][j - weight]:
                dp[i+1][j] = max(dp[i][j], dp[i+1][j - weight] + value)
            else:
                dp[i+1][j] = max(dp[i][j], dp[i+1][j-1])

    for j in range(w + 1):
        if dp[n][j] == dp[n][w]:
            max_w = j
            break

    print("Case {0}".format(case))
    print(dp[n][w])
    print(max_w)

Python: C_num = 1
while True:
    Nap = []
    W = int(input())

    if W == 0:
        break
    N = int(input())
    for i in range(N):
        v,w = map(int,input().split(","))
        Nap.append([v,w])
    DP = [[0 for j in range(W + 1)] for i in range(N + 1)]
    for i in range(1,N+1):
            for j in range(W+1):
                if j - Nap[i-1][1] >= 0:
                    DP[i][j] = max(DP[i-1][j],DP[i - 1][j - Nap[i - 1][1]] + Nap[i - 1][0])
                else:
                    DP[i][j] = DP[i-1][j]
    omo = DP[N].index(DP[N][W])
    print("Case ",C_num,":",sep = "",end = "\n")
    print(DP[N][W])
    print(omo)
    C_num += 1

Python: # coding: utf-8

Python: # coding: utf-8
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):
            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])
    count += 1

Python: def f():
 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])}')
f()

Python: def f():
 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])}')
f()

Python: cnt=0
while 1:
    cnt+=1
    w=int(raw_input())
    if w==0:break
    n=int(raw_input())
    tre=[map(int,raw_input().split(",")) for _ in xrange(n)]
    dp=[[0]*(w+1) for _ in xrange(n+1)]
    dp[0][0]=0
    for i in xrange(n):
        for j in xrange(w+1):
            if tre[i][1]>j:dp[i+1][j]=dp[i][j]
            else:
                dp[i+1][j]=max(dp[i][j],dp[i][j-tre[i][1]]+tre[i][0])
    print('Case '+str(cnt)+":")
    print(dp[n][w])
    print(dp[n].index(dp[n][w]))