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: 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)

Python: import itertools

for dn in itertools.count(1):
    W = int(input())
    if W == 0: break
    N = int(input())
    d = [tuple(map(int, input().split(','))) for _ in range(N)]

    v = [0 for _ in range(W + 1)]
    for i in range(N):
        for j in range(W, d[i][1] - 1, -1):
            v[j] = max(v[j], v[j - d[i][1]] + d[i][0])
    print("Case %d:\n%d\n%d" % (dn, max(v), v.index(max(v))))

Python: from itertools import combinations
from collections import deque
case = 0
while True :
    limit = int(input())
    if limit == 0 : break
    case += 1
    number = int(input())
    
    value, weight = deque(), deque()
    for _ in range(number) :
        a, b = input().split(',')
        value.append(int(a))
        weight.append(int(b))
    
    result = [0, 0]
    for _ in range(1, number+1) :
        temp1 = [sum(_2) for _2 in deque(combinations(value, _))]
        temp2 = [sum(_2) for _2 in deque(combinations(weight, _))]
        for _2 in range(len(temp1)) :
            if (result[0] < temp1[_2] and temp2[_2] <= limit) or (result[0] == temp1[_2] and temp2[_2] < result[1]) : result = temp1[_2], temp2[_2]
    print('Case {}:'.format(case))
    print(result[0])
    print(result[1])

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