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 True:
    w_limit = int(input())
    if not w_limit:
        break
    n = int(input())
    treasures = [tuple(map(int, input().split(','))) for _ in range(n)]

    furoshiki = [0] * (w_limit + 1)
    for v, w in treasures:
        for j in range(w_limit, w - 1, -1):
            furoshiki[j] = max(furoshiki[j], furoshiki[j - w] + v)

    max_v = max_v_w = 0
    for w in range(w_limit + 1):
        if furoshiki[w] > max_v:
            max_v = furoshiki[w]
            max_v_w = w

    print('Case {}:'.format(case))
    print(max_v)
    print(max_v_w)
    case += 1

Python: """
0-1ナップザック
dp[i][j]...i個目までの宝で重さjの時の価値の最大
wi = wlst[i]...i個目の重さ
vi = vlst[i]...i個目の価値
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - wi] + vi)  (wi <= j)
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])                          (wi >  j)
"""


def main():
  case = 0

  while True:
    w = int(input())
    if not w:
      break
  
    case += 1
  
    n = int(input())
  
    vlst = [0]
    wlst = [0]
  
    for _ in range(n):
      vin, win = map(int, input().split(","))
      vlst.append(vin)
      wlst.append(win)

    dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
    
    for i in range(1, n + 1):
      vi, wi = vlst[i], wlst[i]
      dpi = dp[i]
      dpim = dp[i - 1]
      for j in range(1, w + 1):
        if j >= wi:
          dpi[j] = max(dpim[j], dpi[j - 1], dpim[j - wi] + vi)
        else:
          dpi[j] = max(dpim[j], dpi[j - 1])
  
    print("Case " + str(case) + ":")
    print(dp[n][w])

    for i in range(w, -1, -1):
      if dp[n][i] != dp[n][w]:
        print(i + 1)
        break

main()

Python: out = []
cnt = 0
while True:
    W = int(input())
    if W == 0:
        break
    N = int(input())
    v = []
    w = []
    C = list([0 for i in range(W + 1)] for j in range(N + 1))
    for i in range(N):
        n, m = list(map(int,input().split(",")))
        v.append(n)
        w.append(m)
    for i in range(1, N + 1):
        for j in range(1, W + 1):
            if j - w[i - 1] < 0:
                C[i][j] = C[i-1][j]
            else:
                C[i][j] = max(int(C[i-1][j]),int(C[i-1][j-w[i - 1]]+v[i - 1]))
    for i in range(1,W+1):
            if C[N][i] == C[N][W]:
                min_wt = i
                break
    out.append([C[N][W] , min_wt])
    cnt += 1

for cs in range(cnt):
    print("Case "+str(cs+1)+":")
    print(out[cs][0])
    print(out[cs][1])

Python: from sys import stdin

case = 0
while(True):
    case += 1
    W = int(stdin.readline())
    if not W: break
    print("Case %d"%case)
    N = int(stdin.readline())
    v = [0] * N
    w = [0] * N
    dp = [[0]*(W + 1) for _ in range(N + 1)]

    for k in range(N):
        v[k], w[k] = map(int, stdin.readline().split(","))
    for i in range(N-1,-1,-1):
        for j in range(W+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(dp[0][W])
    for i in range(W+1):
        if dp[0][i] == dp[0][W]: print(i); break

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: 

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

casea = 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(casea))
	print(v)
	print(w)
	casea += 1

Python: case = 0
while True:
    W = int(input())
    if W == 0:
        break
    N = int(input())
    case += 1
    # a list of [itemValue, itemWeight]
    items = [list(map(int,input().split(','))) for i in range(N)]
    dp = {}
    def bestVW(item, capa):
        if (item,capa) in dp:
            return dp[(item,capa)]
        elif item == 0:
            bestVWForCapa = items[item] if items[item][1] <= capa else [0,0]
            dp[(item,capa)] = bestVWForCapa
            return bestVWForCapa
        else:
            if items[item][1] > capa:
                bestVWForCapa = bestVW(item-1, capa)
                dp[(item,capa)] = bestVWForCapa
                return bestVWForCapa
            else:
                pickedVW = bestVW(item-1,capa)
                notPickedVW = list(map(sum, zip(items[item], bestVW(item-1, capa-items[item][1]))))
                bestVWForCapa = pickedVW if pickedVW[0] > notPickedVW[0] else notPickedVW 
                dp[(item,capa)] = bestVWForCapa
                return bestVWForCapa
    msg = "Case "+str(case)+":"
    print(msg)
    print('\n'.join(map(str,bestVW(N-1,W))))

Python: caseN = 0
while True:
    caseN += 1
    W = int(input())
    if W == 0: break
    N = int(input())
    tr = [list(map(int, input().split(','))) for _ in range(N)]
    dp = [0 for x in range(W+1)]
    for x in range(N):
        for y in range(W,tr[x][1]-1,-1):
            dp[y] = max(dp[y], dp[y-tr[x][1]] + tr[x][0])
    sum_weight = 0
    sum_value = 0
    ind = N%2
    for x in range(W+1):
        if dp[x] > sum_value:
            sum_weight = x
            sum_value = dp[x]
    print("Case ", caseN, ":", sep='')
    print(sum_value)
    print(sum_weight)