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: cnt=0
while True:
    cnt+=1
    W=int(input())
    if W==0:
        break
    n=int(input())
    dp=[0]*(W+1)
    for i in range(n):
        v,w=map(int,input().split(','))
        for j in range(W,w-1,-1):
            dp[j]=max(dp[j],dp[j-w]+v)
    wgt=0
    md=max(dp)
    for i in range(W+1):
        if md==dp[i]:
            wgt=i
            break
    print("Case {0}:".format(cnt))
    print(md)
    print(wgt)

Python: while True:
    cnt = 0
    cnt += 1
    maxweight = int(input())
    if maxweight == 0:
        break
    length = int(input())
    tresure = []
    dp = [[0 for n in range(length+1)] for m in range(maxweight + 1)]
    answeight = 0
    ansvalue = 0
    for l in range(length):
        v,w = (int(n) for n in input().split(","))
        tresure.append([v,w])
    for outer in range(length + 1):
        if outer == 0:
            continue
        weight = tresure[outer-1][1]
        value = tresure[outer-1][0]
        dp[weight][outer] = max(dp[weight][outer],value)
        for inner in range(maxweight + 1):
            if dp[inner][outer - 1] != 0:
                beforevalue = dp[inner][outer - 1]
                beforeweight = inner
                dp[inner][outer]  = max(beforevalue,dp[inner][outer])
                if beforeweight + weight <= maxweight:
                    nowvalue = dp[beforeweight + weight][outer]
                    dp[beforeweight + weight][outer] = max(nowvalue,beforevalue+value)
    #print(dp)
    for a in range(maxweight+1):
        #print(dp[a][length])
        if ansvalue < dp[a][length]:
            ansvalue = dp[a][length]
            answeight = a
    print("Case {0}:".format(cnt))
    print(ansvalue)
    print(answeight)

Python: count=1
while True:
    vw=[[0,0]]
    W=int(input())
    if W==0:
        break
    n=int(input())
    for i in range(n):
        vw.append(list(map(int,input().split(','))))
    
    dp=[]
    weight=[]
    
    for _ in range(n+1):
        dp.append([0 for i in range(W+1)])
        weight.append([0 for i in range(W+1)])
    for i in range(1,n+1):
        for j in range(0,W-vw[i][1]+1):
            dp[i][j+vw[i][1]]=max(dp[i-1][j+vw[i][1]],dp[i-1][j]+vw[i][0])
            if dp[i][j+vw[i][1]]==dp[i-1][j]+vw[i][0]:
                weight[i][j+vw[i][1]]=weight[i-1][j]+vw[i][1]
            else:
                weight[i][j+vw[i][1]]=weight[i-1][j]
            
    print('Case '+'{}'.format(count)+':')
    print(dp[n][W])
    print(weight[n][W])
    count+=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):
   t=d[i-w]+v
   if d[i]<t:d[i]=t
 print(f'Case {c}:\n{d[W]}\n{d.index(d[W])}')

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 >= wlst[i]:
          dpi[j] = max(dpim[j], dpi[j - 1], dpim[j - wi] + vi)
        else:
          dpi[j] = max(dpi[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: case = 0
while True:
    W = int(input())
    if W == 0:
        break
    N, case = int(input()), case + 1
    items = [[0,0]] + [list(map(int, input().split(','))) for _ in range(N)]
    C = [[0 for _ in range(W+1)] for _ in range(N+1)]
    for i in range(1, N+1):
        for w in range(1, W+1):
            if items[i][1] <= w:
                C[i][w] = max(items[i][0]+C[i-1][w-items[i][1]], C[i-1][w])
            else:
                C[i][w] = C[i-1][w]
    maxv = max(C[-1])
    print("Case {0}:\n{1}\n{2}".format(case, maxv, C[-1].index(maxv)))

Python: cnt=0
while True:
    cnt+=1
    W=int(input())
    if W==0:
        break
    n=int(input())
    dp=[0]*(W+1)
    for i in range(n):
        v,w=map(int,input().split(','))
        for j in range(W,w-1,-1):
            dp[j]=max(dp[j],dp[j-w]+v)
    wgt=0
    md=max(dp)
    for i in range(W+1):
        if md==dp[i]:
            wgt=i
            break
    print("Case {0}:".format(cnt))
    print(md)
    print(wgt)

Python: # i????????\??????????????§??????j??§??????(?????§??????, -??????????????????)
def ns(vs, ws, i, j, dp):
    if dp[i][j][0] != -1:
        return dp[i][j]
    if i == len(vs):
        return [0, 0]
    else:
        if ws[i] > j:
            dp[i][j] = ns(vs, ws, i+1, j, dp)
            return dp[i][j] 
        else:
            tmp = ns(vs, ws, i+1, j-ws[i], dp)
            dp[i][j] = max(ns(vs, ws, i+1, j, dp), [vs[i]+tmp[0], -ws[i]+tmp[1]], key = lambda x: (x[0], x[1]))
            return dp[i][j]

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)

    dp = [[[-1, -1] for _ in range(W+1)] for __ in range(N+1)]
    v, w = ns(vs, ws, 0, W, dp)
    print('Case ' + str(casenum) + ':')
    print(v)
    print(-w)
    casenum += 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]))