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: 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-1][j+vw[i][1]]==dp[i-1][j]+vw[i][0]:
                weight[i][j+vw[i][1]]=min(weight[i-1][j]+vw[i][1],weight[i-1][j+vw[i][1]])  
            elif 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+vw[i][1]]
    print('Case '+'{}'.format(count)+':')
    print(dp[n][W])
    print(weight[n][W])
    count+=1

Python: c=1
while 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-w]+v,dp[j])
    for i in range(W):
        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])}')

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

case = 0
while True:
    case += 1
    w_max = int(input())
    if w_max == 0:
        break
    n = int(input())
    t = []
    for i in range(n):
        t.append(list(map(int, input().split(","))))
    v_best = 0
    w_best = w_max
    p_all = itertools.product([0,1], repeat=n)
    for p in p_all:
        v = 0
        w = 0
        for i in range(n):
            v += p[i]*t[i][0]
            w += p[i]*t[i][1]
        if v > v_best and w < w_max:
            v_best = v
            w_best = w
        elif v == v_best and w < w_best:
            v_best = v
            w_best = w
    print("Case:",case)
    print(v_best)
    print(w_best)

Python: case = 0
while True:
  case += 1
  W = int(input())
  if (W == 0):
    break
  N = int(input())
  vl = [0]
  wl = [0]
  for i in range(N):
    (v,w) = tuple(map(int,input().split(",")))
    vl.append(v)
    wl.append(w)
  dp = [[0 for i in range(W+1)] for j in range(N+1)]
  for i in range(1,N+1):
    for j in range(1,W+1):
      if j >= wl[i]:
        dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-wl[i]] + vl[i])
      else:
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  print("Case " + str(case) + ":")
  print(dp[N][W])
  for i in range(W+1):
    if dp[N][i] == dp[N][W]:
      print(i)
      break

Python: """
0-1ナップザック
wi = wlst[i]...i個目の重さ
vi = vlst[i]...i個目の価値

2次元

dp[i][j]...i個目までの宝で重さjの時の価値の最大
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)

or

dp[j]...重さjの時の価値の最大
temp...1つ前のdp
dp[j] = max(dp[j], dp[j - 1], temp[j - wi] + vi)  (wi <= j)
dp[j] = max(dp[j], dp[j - 1])                     (wi >  j)

"""

INF = 10 ** 20

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 i in range(1, n + 1):
      vi, wi = vlst[i], wlst[i]
      temp = dp[:]
      for j in range(1, w + 1):
        if j >= wi:
          dp[j] = max(dp[j], dp[j - 1], temp[j - wi] + vi)
        else:
          dp[j] = max(dp[j], dp[j - 1])
  
    print("Case " + str(case) + ":")
    print(dp[w])
    print(dp.index(dp[w]))
main()

Python: c=1
while 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-w]+v,dp[j])
    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: 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
    print('Case ',case, ':', sep='')
    print('\n'.join(map(str,bestVW(N-1,W))))

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