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
}

Python: case = 1

while 1:
	W = int(input())
	if W == 0:
		break
	N = int(input())

	v = []
	w = []

	for _ in range(N):
		v_, w_ = map(int,input().split(","))
		v.append(v_)
		w.append(w_)

	dp = [[0 for _ in range(W)] for _ in range(N)]
	for i in range(w[0],W):
		dp[0][i] = v[0]

	for i in range(1, N):
		for j in range(W):
			if j - w[i] < 0:
				dp[i][j] = dp[i-1][j]
			else:
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])

	res = dp[N-1][W-1]
	minw = min([i for i in range(W) if dp[N-1][i] == res])

	print("Case "+str(case)+":")
	print(res)
	print(minw)
	case += 1

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):
            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: # AOJ 0042 A Thief
# Python3 2018.6.22 bal4u

MAX = 1003

for cno in range(1, 100):
	lim = int(input())
	if lim == 0: break
	print("Case ", cno, ":", sep='')
	N = int(input())
	V = [[0 for j in range(MAX)] for i in range(2)]
	W = [[0 for j in range(MAX)] for i in range(2)]		
	k1, k2 = 0, 1
	for i in range(1, N+1):
		v, w = map(int, input().split(','))
		for j in range(1, w):
			V[k2][j] = V[k1][j]
			W[k2][j] = W[k1][j]
		for j in range(w, lim+1):
			d = j - w
			if V[k1][d] + v >= V[k1][j]:
				V[k2][j] = V[k1][d] + v
				W[k2][j] = W[k1][d] + w
			else:
				V[k2][j] = V[k1][j]
				W[k2][j] = W[k1][j]
		k1, k2 = k2, k1
	print(V[k1][lim], W[k1][lim], sep='\n')

Python: import itertools

case = 0
while True:
    case += 1
    w_max = int(input())
    if w_max == 0:
        break
    n = int(input())
    t = []
    for i in range(n):
        t.append(list(map(int, input().split(","))))
    v_best = 0
    w_best = 0
    p_all = itertools.product([0,1], repeat=n)
    for p in p_all:
        v = 0
        w = 0
        for i in range(n):
            v += p[i]*t[i][0]
            w += p[i]*t[i][1]
        if v > v_best and w < w_max:
            v_best = v
            w_best = w
        elif v == v_best and w < w_best:
            v_best = v
            w_best = w
    print("Case ",case,":",sep="")
    print(v_best)
    print(w_best)

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):
            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 rec(i, j):
	if dp[i][j] != -1:
		return dp[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
	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)]
	v, w = rec(0, W)

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

Python: import itertools

case = 0
while True:
    case += 1
    w_max = int(input())
    if w_max == 0:
        break
    n = int(input())
    t = []
    for i in range(n):
        t.append(list(map(int, input().split(","))))
    v_best = 0
    w_best = 0
    p_all = itertools.product([0,1], repeat=n)
    for p in p_all:
        v = 0
        w = 0
        for i in range(n):
            v += p[i]*t[i][0]
            w += p[i]*t[i][1]
        if v > v_best and w < w_max:
            v_best = v
            w_best = w
        elif v == v_best and w < w_best:
            v_best = v
            w_best = w
    print("Case",case,":")
    print(v_best)
    print(w_best)

Python: import itertools

case = 0
while True:
    case += 1
    w_max = int(input())
    if w_max == 0:
        break
    n = int(input())
    t = []
    for i in range(n):
        t.append(list(map(int, input().split(","))))
    v_best = 0
    w_best = 0
    p_all = itertools.product([0,1], repeat=n)
    for p in p_all:
        v = 0
        w = 0
        for i in range(n):
            v += p[i]*t[i][0]
            w += p[i]*t[i][1]
        if v > v_best and w < w_max:
            v_best = v
            w_best = w
        elif v == v_best and w < w_best:
            v_best = v
            w_best = w
    print("Case:",case)
    print(v_best)
    print(w_best)