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: class Knapack(object):
    def __init__(self, data, limit):
        self.limit = limit
        data_size = len(data)
        self.C = [[0]*(limit+1) for _ in range(data_size+1)]
        self.data = data[:]

    def solve(self):
        for i in range(1, len(self.data)+1):
            i_value = self.data[i-1][0]
            i_weight = self.data[i-1][1]
            for w in range(1, self.limit+1):
                if i_weight <= w:
                    if i_value + self.C[i-1][w-i_weight] > self.C[i-1][w]:
                        self.C[i][w] = i_value + self.C[i-1][w-i_weight]
                    else:
                        self.C[i][w] = self.C[i-1][w]
                else:
                    self.C[i][w] = self.C[i-1][w]


if __name__ == '__main__':
    # ??????????????\???
    # limit = 50
    # data = [[60, 10], [100, 20], [120, 30], [210, 45], [10, 4]]
    case_no = 1
    while True:
        limit = int(input())
        if limit == 0:
            break
        num_of_items = int(input())
        data = []
        for i in range(num_of_items):
            data.append(list(map(int, input().split(','))))

        # ????????????????????????????§£???
        ks = Knapack(data, limit)
        ks.solve()

        # ???????????¨???
        target = ks.C[len(data)][limit]
        weight = limit
        for w in range(limit, 0, -1):
            if ks.C[len(data)][w] == target:
                weight = w
        print('Case {0}:'.format(case_no))
        print('{0}\n{1}'.format(target, weight))
        case_no += 1

Python: #coding:utf-8

from __future__ import division, print_function
try:
    input = raw_input
    range = xrange
except NameError:
    pass


def solve(cnt, W, N, treasures):
    dp = [0] + [-1] * W
    for v, w in treasures:
        for j in range(W, w - 1, -1):
            if dp[j - w] >= 0:
                dp[j] = max(dp[j], dp[j - w] + v)

    ans = max(dp)
    print('Case %d:\n%d\n%d' % (cnt, ans, dp.index(ans)))

cnt = 1
while True:
    W = int(input())
    if W == 0:
        break
    N = int(input())
    
    treasures = [tuple(map(int, input().split(','))) for _ in range(N)]
    solve(cnt, W, N, treasures)

    cnt += 1

Python: 

def rec(i, j):
	#print("rec({}, {}) called".format(i, j))
	"""
	if dp[i][j] != -1:
		return dp[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: 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))
    
    temp1, temp2 = [], []
    for _ in range(1, number+1) : 
        temp1.append(list(combinations(value, _)))
        temp2.append(list(combinations(weight, _)))
    temp1, temp2 = sum(temp1, []), sum(temp2, [])
    value, weight = [], []
    for _ in temp1 : value.append(sum(_))
    for _ in temp2 : weight.append(sum(_))
    
    result = [0, 0]
    for _ in range(len(temp1)) :
        if result[0] < value[_] and weight[_] <= limit :
            result = value[_], weight[_]
        elif result[0] == value and weight[_] < result[1] :
            result = value[_], weight[_]
    print('Case {}:'.format(case))
    print(result[0])
    print(result[1])

Python: import itertools

def solve(W, N, v):
    cache = {}
    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(W, N, v)
    print("Case %d:\n%d\n%d" % (dn, optim[0], optim[1]))

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

Python: def memoize(f):
    memo = {}

    def main(*args):
        if args in memo:
            return memo[args]
        result = memo[args] = f(*args)
        return result

    return main


@memoize
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: c=1
while 1:
    W=int(input())
    if W==0:break
    dp=[0]*(W+1)
    for i in range(int(input())):
        v,w = map(int, input().split(','))
        for j in range(W,w-1,-1):
            if dp[j]<dp[j-w]:dp[j]=dp[j-w]
    for i in range(W+1):
        if dp[W]==dp[i]:break
    print('Case %d:\n%d\n%d'%(c,dp[W],i))
    c+=1

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