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: import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve(k):
    W = int(readline())
    if W == 0:
        return False
    INF = 10**18
    dp = [-INF]*(W+1)
    dp[0] = 0
    N = int(readline())
    for i in range(N):
        v, w = map(int, readline().split(","))
        for j in range(W-w, -1, -1):
            dp[j+w] = max(dp[j+w], dp[j] + v)
    vm = max(dp)
    wm = dp.index(vm)
    write("Case %d:\n%d\n%d\n" % (k, vm, wm))
    return True
i = 1
while solve(i):
    i += 1

Python: def ns(vs, ws, i, j):
    if i == len(vs):
        return [0, 0]
    else:
        if ws[i] > j:
            return ns(vs, ws, i+1, j)
        else:
            vwoi, wwoi = ns(vs, ws, i+1, j)
            tmp = ns(vs, ws, i+1, j-ws[i])
            return max(ns(vs, ws, i+1, j), [vs[i]+tmp[0], ws[i]+tmp[1]], key = lambda x: x[0])

casenum = 1
while True:
    W = int(input())
    if W == 0:
        break
    N = int(input())
    vs, ws = [], []
    for _ in range(N):
        v, w = map(int, input().split(','))
        vs.append(v)
        ws.append(w)

    v, w = ns(vs, ws, 0, W)
    print('Case ' + str(casenum) + ':')
    print(v)
    print(w)
    casenum += 1

Python: def furoshiki(i, w_limit):
    global treasures
    if not i or not w_limit:
        return (0, 0)

    v, w = treasures[i - 1]
    not_stole = furoshiki(i - 1, w_limit)
    if w_limit < w:
        return not_stole
    stole_v_total, stole_w_total = furoshiki(i - 1, w_limit - w)
    stole_v_total += v
    stole_w_total -= w
    return max(not_stole, (stole_v_total, stole_w_total))


case = 1
while True:
    w = int(input())
    if not w:
        break
    n = int(input())
    treasures = [None] * n
    for i in range(n):
        treasures[i] = tuple(map(int, input().split(',')))

    total_v, total_w = furoshiki(n, w)
    print('Case {}:'.format(case))
    print(total_v)
    print(-total_w)
    case += 1

Python: from itertools import combinations
case = 0
while True :
    limit = int(input())
    if limit == 0 : break
    case += 1
    number = int(input())
    
    value, weight = [], []
    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 list(combinations(value, _))]
        temp2 = [sum(_2) for _2 in list(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: 

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 python3
# -*- coding: utf-8 -*-
import itertools

def solve():
    cache = dict()
    def loop(i, w):
        if (i, w) in cache:
            return cache[i, w]
        if i == N:
            return (0, 0)
        cache[i, w] = loop(i + 1, w)
        if v[i][1] <= w:
            t = loop(i + 1, w - v[i][1])
            cache[i, w] = max(cache[i, w], (t[0] + v[i][0], t[1] + v[i][1]), key=lambda u: u[0])
        return cache[i, w]
    return loop(0, W)

for dn in itertools.count(1):
    W = int(input())
    if W == 0: break
    N = int(input())
    v = [tuple(map(int, input().split(','))) for _ in range(N)]
    optim = solve()
    print("Case %d:\n%d\n%d" % (dn, optim[0], optim[1]))

Python: cnt = 1
while 1:
    l = int(input())
    if l == 0:
        break
    n = int(input())
    v = [0] * (n+1)
    w = [0] * (n+1)

    for i in range(1, n+1):
        v[i], w[i] = map(int, input().split(','))

    dp = [[0]*(l+1) for i in range(n+1)]

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

    print('Case ', cnt, ':', sep='')
    print(dp[n][l])
    for i in range(l + 1):
        if dp[n][l] == dp[n][i]:
            print(i)
            break
    cnt += 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(1100)] for i in range(1100)]
	v, w = rec(0, W)
	
	print("Case {}:".format(case))
	print(v)
	print(w)
	case += 1