Problem:


泥棒

宝物がたくさん収蔵されている博物館に、泥棒が大きな風呂敷を一つだけ持って忍び込みました。盗み出したいものはたくさんありますが、風呂敷が耐えられる重さが限られており、これを超えると風呂敷が破れてしまいます。そこで泥棒は、用意した風呂敷を破らず且つ最も価値が高くなるようなお宝の組み合わせを考えなくてはなりません。

風呂敷が耐えられる重さ W、および博物館にある個々のお宝の価値と重さを読み込んで、重さの総和が W を超えない範囲で価値の総和が最大になるときの、お宝の価値総和と重さの総和を出力するプログラムを作成してください。ただし、価値の総和が最大になる組み合わせが複数あるときは、重さの総和が小さいものを出力することとします。

Input

複数のデータセットが与えられます。各データセットは以下のような形式で与えられます。

W
N
v1,w1
v2,w2
:
vN,wN

１行目に風呂敷の耐えられる重さを表す整数 W (W ≤ 1,000)、２行目にお宝の数 N (1 ≤ N ≤ 1,000) が与えられます。続く N 行に i 番目のお宝の価値を表す整数 vi (0 ≤ vi ≤ 10,000) とその重さを表す整数 wi (0 ≤ wi ≤ W) の組がそれぞれ１行に与えられます。

W が 0 のとき入力の最後とします。データセットの数は 50 を超えません。

Output

各データセットに対して以下のように出力して下さい。

Case データセットの番号:
風呂敷に入れたお宝の価値総和
そのときのお宝の重さの総和

Sample Input

50
5
60,10
100,20
120,30
210,45
10,4
50
5
60,10
100,20
120,30
210,45
10,4
0

Output for the Sample Input

Case 1:
220
49
Case 2:
220
49



Sample input:
50
5
60,10
100,20
120,30
210,45
10,4
50
5
60,10
100,20
120,30
210,45
10,4
0


Sample output:
Case 1:
220
49
Case 2:
220
49

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
for c in range(1,51):
    W = int(input())
    if W == 0: break
    N = int(input())
    dp = [0 for w in range(W+1)]
    for i in range(N):
        v,w = map(int,input().split(','))
        for j in range(W-w,-1,-1):
            if dp[j] == 0 and j > 0: continue
            dp[j+w] = max(dp[j+w], dp[j] + v)
    ansv = answ = 0
    for w,v in enumerate(dp):
        if v > ansv:
            ansv = v
            answ = w
    print('Case ' + str(c) + ':')
    print(ansv)
    print(answ)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools

case = 0
while True:
    case += 1
    w_max = int(input())
    if w_max == 0:
        break
    n = int(input())

    w = [0 for i in range(n)]
    v = [0 for i in range(n)]
    for i in range(n):
        a, b = map(int, input().split(","))
        v[i] = a
        w[i] = b

    dp = [[0 for j in range(w_max + 1)] for i in range(n + 1)]
    for i in range(n)[::-1]:
        for j in range(w_max + 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("Case ",case,":",sep="")
    print(max(dp[0]))
    print(dp[0].index(max(dp[0])))

Submission status: Accepted

Solution code:
case = 0
while True:
    case += 1
    w_max = int(input())
    if w_max == 0:
        break
    n = int(input())

    w = [0 for i in range(n)]
    v = [0 for i in range(n)]
    for i in range(n):
        a, b = map(int, input().split(","))
        v[i] = a
        w[i] = b

    dp = [[0 for j in range(w_max + 1)] for i in range(n + 1)]
    for i in range(n)[::-1]:
        for j in range(w_max + 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("Case ",case,":",sep="")
    print(max(dp[0]))
    print(dp[0].index(max(dp[0])))

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
c=0
while True:
    W=int(input())#重さの上限
    if W==0:
        break
    c+=1
    N=int(input())#宝物の数

    vl=[0]#価値のリスト
    wl=[0]#重さのリスト
    for i in range(N):
        [v,w]=list(map(int,input().split(",")))#vとwのリストを作る
        vl.append(v)
        wl.append(w)
    #横がW+1で縦がN+1の表を作成する
    dp=[[0 for i in range(W+1)]for j in range(N+1)]
    #表を埋める
    for i in range(N+1):
        for j in range(W+1):
            if i==0 or j==0:
                dp[i][j]=0
            else:
                if wl[i]<=j:
                    dp[i][j]=max(dp[i-1][j-wl[i]]+vl[i],dp[i-1][j])
                else:
                    dp[i][j]=dp[i-1][j]

    #print(dp)
    ls=dp[N].copy()
    ls.reverse()
    #print(ls)
    max_w=W
    for i in range(1,W+1):
        if ls[i]==dp[N][W]:
            max_w-=1
        else:
            break
    print("Case "+str(c)+":")
    print(dp[N][W])
    print(max_w)

Submission status: Accepted

Solution code:
c=0
for W in iter(input,'0'):
 c+=1
 W=int(W)
 dp=[0]*-~W
 for _ in[0]*int(input()):
  v,w=map(int,input().split(','))
  for i in range(W,w-1,-1):
   if dp[i]<dp[i-w]+v:dp[i]=dp[i-w]+v
 for i in range(W+1):
  if dp[W]==dp[i]:print(f'Case {c}:\n{dp[W]}\n{i}');break

Submission status: Accepted

Solution code:
c=0
for W in iter(input,'0'):
 c+=1
 W=int(W)
 dp=[0]*-~W
 for _ in[0]*int(input()):
  v,w=map(int,input().split(','))
  for i in range(W,w-1,-1):
   if dp[i]<dp[i-w]+v:dp[i]=dp[i-w]+v
 print(f'Case {c}:\n{dp[W]}\n{dp.index(dp[W])}')

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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])}')
if'__main__'==__name__:f()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
"""
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()

Submission status: Accepted

Solution code:
"""
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()

Submission status: Accepted

Solution code:
"""
0-1ナップザック
wi...i個目の重さ
vi...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)


1次元

dp[j]...重さjの時の価値の最大
dp[j] = max(dp[j], dp[j - wi] + vi)  (wi <= j <= w)

wi <= j <= wについて更新(j < wiについては変化が無いため更新不要)
前から更新すると更新した結果を使って更新してしまうため後ろから更新
"""

INF = 10 ** 20

def main():
  case = 0

  while True:
    w = int(input())
    if not w:
      break
  
    case += 1
  
    n = int(input())
  
    dp = [0 for _ in range(w + 1)]
    
    for i in range(1, n + 1):
      vi, wi = map(int, input().split(","))
      for j in range(w, wi - 1, -1):
        dp[j] = max(dp[j], dp[j - wi] + vi)
  
    print("Case " + str(case) + ":")
    print(dp[w])
    print(dp.index(dp[w]))
main()

Submission status: Accepted

Solution code:
nCase = 0
while True:
    W = int(input())
    if W == 0: break
    nCase += 1
    N = int(input())
    # [(value, weight), ... ]
    items = [tuple(map(int, input().split(','))) for _ in range(N)]
    bestValueFor = [0] * (W + 1) # item -> best value, idx -> capacity 
    for item in items:
        for capa in reversed(range(W-item[1]+1)):
            # if taken wins not taken
            if bestValueFor[capa] + item[0] > bestValueFor[capa + item[1]]:
                bestValueFor[capa + item[1]] = bestValueFor[capa] + item[0]
    bestValue = max(bestValueFor)
    bestWeight = bestValueFor.index(bestValue)
    print('Case ',str(nCase),':',sep='')
    print(bestValue)
    print(bestWeight)

Submission status: Accepted

Solution code:
# AOJ 0042 A Thief
# Python3 2018.6.22 bal4u

MAX = 1003

for cno in range(1, 100):
	lim = int(input())
	if lim == 0: break
	print("Case ", cno, ":", sep='')
	N = int(input())
	vw = [(0, 0)]
	for i in range(N):
		v, w = list(map(int, input().split(',')))
		vw.append((v, w))

	V = [[0 for j in range(MAX)] for i in range(2)]
	W = [[0 for j in range(MAX)] for i in range(2)]		
	k1, k2 = 0, 1
	for i in range(1, N+1):
		for j in range(1, lim+1):
			v, w = vw[i]
			if w > j:
				V[k2][j] = V[k1][j]
				W[k2][j] = W[k1][j]
			else:
				d = j - w
				if V[k1][d] + v >= V[k1][j]:
					V[k2][j] = V[k1][d] + v
					W[k2][j] = W[k1][d] + w
				else:
					V[k2][j] = V[k1][j]
					W[k2][j] = W[k1][j]
		k1, k2 = k2, k1
	print(V[k1][lim], W[k1][lim], sep='\n')

Submission status: Accepted

Solution code:
# AOJ 0042 A Thief
# Python3 2018.6.22 bal4u

MAX = 1003

for cno in range(1, 100):
	lim = int(input())
	if lim == 0: break
	print("Case ", cno, ":", sep='')
	N = int(input())
	V = [[0 for j in range(MAX)] for i in range(2)]
	W = [[0 for j in range(MAX)] for i in range(2)]		
	k1, k2 = 0, 1
	for i in range(1, N+1):
		v, w = map(int, input().split(','))
		for j in range(1, w):
			V[k2][j] = V[k1][j]
			W[k2][j] = W[k1][j]
		for j in range(w, lim+1):
			d = j - w
			if V[k1][d] + v >= V[k1][j]:
				V[k2][j] = V[k1][d] + v
				W[k2][j] = W[k1][d] + w
			else:
				V[k2][j] = V[k1][j]
				W[k2][j] = W[k1][j]
		k1, k2 = k2, k1
	print(V[k1][lim], W[k1][lim], sep='\n')

Submission status: Accepted

Solution code:
case=0
while True:
    case+=1
    W=input()
    if W==0:break
    print "Case {}:".format(case)
    dp=[0]*1001
    w=[0]*1001
    v=[0]*1001
    n=input()
    for i in xrange(n):
        v[i],w[i]=map(int,raw_input().strip().split(","))
    for i in xrange(n):
        for j in xrange(W,-1,-1):
            if j+w[i]<=W:
                dp[j+w[i]]=max(dp[j+w[i]],dp[j]+v[i])
    print max(dp)
    print dp.index(max(dp))

Submission status: Accepted

Solution code:
num=1
while True:
    maxw=input()
    if maxw==0:break
    print "Case %d:"%num
    dp,w,v=[0]*1001,[0]*1001,[0]*1001
    n=input()
    for i in xrange(n):
        v[i],w[i]=map(int,raw_input().strip().split(","))
    for i in xrange(n):
        for j in xrange(maxw,-1,-1):
            if j+w[i]<=maxw:
                dp[j+w[i]]=max(dp[j+w[i]],dp[j]+v[i])
    print max(dp)
    print dp.index(max(dp))
    num+=1

Submission status: Accepted

Solution code:

import sys
import itertools


class Treasure:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight



def solv(treasures, w_limit):
    dp = []
    dp.append(0)
    for n in range(w_limit):
        dp.append(-1)
    for i in treasures:
        for j in range(w_limit - i.weight, -1, -1):
            if dp[j] >= 0:
                dp[j + i.weight] = max(dp[j + i.weight], dp[j] + i.value)
    p = 0
    q = 0
    for i in range(w_limit + 1):
        if dp[i] > p:
            p = dp[i]
            q = i
    return (p, q)






case = 0

while True:
    weight_limit = int(sys.stdin.readline())
    case += 1
    if weight_limit == 0:
        exit()
    n = int(sys.stdin.readline())
    treasures = []
    for i in range(n):
        v, w = map(int, sys.stdin.readline().split(','))
        treasures.append(Treasure(v, w))
    value, weight = solv(treasures, weight_limit)
    print 'Case ' + str(case) + ':'
    print value
    print weight

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin
from itertools import count

def douteki(limit, data):
    V = [[0 for w in xrange(limit+1)] for i in xrange(len(data)+1)]
    W = [[0 for w in xrange(limit+1)] for i in xrange(len(data)+1)]
    for i in xrange(len(data)+1):
        for w in xrange(limit+1):
            diff = w - data[i-1][1]
            if i - 1 >= 0 and diff >= 0:
                v1 = V[i-1][diff] + data[i-1][0]
                w1 = W[i-1][diff] + data[i-1][1]
            else:
                v1 = 0
                w1 = 0
            v2 = V[i-1][w]
            w2 = W[i-1][w]

            V[i][w], W[i][w] = (v1, w1) if v1 >= v2 else (v2, w2)
    return V[-1][-1], W[-1][-1]

for case in count(1):
    W = int(stdin.readline())
    if not W:
        break

    N = int(stdin.readline())
    data = []
    for _ in xrange(N):
        data.append([int(s) for s in stdin.readline().split(',')])

    value, weight = douteki(W, data)
    print('Case {}:\n{}\n{}'.format(case, value, weight))

Submission status: Accepted

Solution code:
case = 0
while True:
    w = int(raw_input())
    if w == 0:
        break
    n = int(raw_input())
    dp = [[0] * 1001 for i in range(1001)]
    r1,r2 = 0,0
    for i in range(1, n + 1):
        a,b = map(int, raw_input().split(','))
        for j in range(w + 1):
            if j - b >= 0:
                dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - b] + a)
            else:
                dp[i][j] = dp[i - 1][j]
            if r1 <= dp[i][j]:
                if r1 == dp[i][j]:
                    r2 = min(r2, j)
                else:
                    r2 = j
                    r1 = dp[i][j]
    case += 1
    print 'Case {}:'.format(case)
    print r1
    print r2

Submission status: Accepted

Solution code:
count =0
while True:
    W = input()
    if (W==0): break
    work={0:0}
    count +=1
    N = input()
    for i in range(N):
        p,w = input()
        for w0 in sorted(work.keys(),reverse=True):
            w1 = w0+w
            p1 = work[w0]+p
            if w1>W or (work.has_key(w1) and work[w1]>=p1): continue
            else: work[w1] = p1

    m = max(work.values())
    tmp = work.values().index(m)
    n = work.keys()[tmp]
    print "Case %d:" %(count)
    print m
    print n

Submission status: Accepted

Solution code:
count =0
while True:
    W = input()
    if W==0: break
    work = [0]*1001
    count +=1
    N = input()
    m = 0
    n = 0
    for i in range(N):
        p,w = input()
        for w0 in range(W+1)[::-1]:
            p0 = work[w0]
            if w0>0 and p0==0: continue
            w1 = w0+w
            p1 = p0+p
            if w1<=W and work[w1]<p1:
                work[w1] = p1
                if m<p1:
                    m = p1
    n = work.index(m)
    print "Case {}:".format(count)
    print m
    print n

Submission status: Accepted

Solution code:
c =0
while True:
    W = input()
    if W==0: break
    dt = [0]*1001
    c +=1
    N = input()
    m = 0
    n = 0
    for i in range(N):
        p,w = input()
        for w0 in range(W+1)[::-1]:
            p0 = dt[w0]
            if w0==0 or p0!=0:
                w1 = w0+w
                p1 = p0+p
                if w1<=W and dt[w1]<p1: dt[w1]=p1
    m = max(dt)
    n = dt.index(m)
    print "Case {}:".format(c)
    print m
    print n

Submission status: Accepted

Solution code:
case = 1

while 1:
    W = input()
    if W == 0: break
    N = input()
    v, w = [0]*N, [0]*N
    for i in range(N):
        v[i], w[i] = map(int, raw_input().split(','))
    dp = [0]*(W+1)
    for i in range(N):
        for j in range(W,0,-1):
            if j-w[i] >= 0:
                dp[j] = max(dp[j-w[i]]+v[i], dp[j])
    av, aw = 0, 0
    for w, v in enumerate(dp):
        if av < v:
            av = v
            aw = w
    print 'Case {}:'.format(case)
    print av
    print aw
    case += 1

Submission status: Accepted

Solution code:
def f():
    p,w = input()
    for w0 in R[w:]:
        w1,p1 = w0+w,dt[w0]+p
        if dt[w1]<p1: dt[w1]=p1
    return

c = 0
while 1:
    W = input()
    if W==0: break
    R = range(W+1)[::-1]
    dt = [0]*1001
    c += 1
    N = input()
    for i in range(N): f()
    m = max(dt)
    n = dt.index(m)
    print "Case {}:\n{}\n{}".format(c,m,n)

Submission status: Accepted

Solution code:
def get():
	p,w = map(int, raw_input().split(","))
	for i in range(W-w,-1,-1):
		if bag[i] > 0 and bag[i]+p > bag[i+w]:
			bag[i+w] = bag[i]+p
	else:
		if p > bag[w]: bag[w] = p
	return

c = 1
while True:
	W = int(raw_input())
	if W == 0: break
	bag = [0]*(W+1)
	N = int(raw_input())
	for i in range(N): get()
	w_all = max(bag)
	money = bag.index(w_all)
	print "Case {}:\n{}\n{}".format(c,w_all,money)
	c += 1

Submission status: Accepted

Solution code:
from itertools import *

def mlist(n, *args, **keys):
    if args:
        return [mlist(*args, **keys) for i in range(n)]
    else:
        return [keys.get('default')] * n

for h in count(1):
    w = int(raw_input())
    if w == 0: break
    n = int(raw_input())
    a, b = zip(*[map(int, raw_input().split(',')) for i in range(n)])
    c = mlist(1010, 1010)
    c[0][0] = 0
    for i in range(n):
        for j in range(w + 1):
            if c[i][j] is None: continue
            c[i + 1][j] = max(c[i + 1][j], c[i][j])
            if j + b[i] <= w:
                c[i + 1][j + b[i]] = max(c[i + 1][j + b[i]], c[i][j] + a[i])
    mx = max(c[n])
    print 'Case {}:'.format(h)
    print mx
    print c[n].index(mx)

Submission status: Accepted

Solution code:
#!/bin/env python3
# -*- coding: utf-8 -*-
from __future__ import division, print_function
try:
    input = raw_input
    range = xrange
except NameError:
    pass
# 上記のコードはPython2とPython3の違いを一部吸収するためのもの


def main():
    value = [0] * 1000
    weight = [0] * 1000
    casenum = 1
    while True:
        W = int(input())
        if(W == 0):
            return
        N = int(input())
        dp = [[0 for x in range(W+1)] for y in range(N+1)]
        for x in range(0, N):
            value[x], weight[x] = map(int, input().split(','))
        for i in range(0, N):
            for w in range(0, W+1):
                if w - weight[i] >= 0:
                    use = dp[i][w - weight[i]] + value[i]
                else:
                    use = 0
                unuse = dp[i][w]
                dp[i+1][w] = max(use, unuse)
        print("Case " + str(casenum) + ":")
        for w in range(W+1):
            if(dp[N][w] == dp[N][W]):
                print(str(dp[N][w]) + "\n" + str(w))
                break
        casenum += 1
main()

Submission status: Accepted

Solution code:
#coding:utf-8

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


def solve(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)
    return 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)]
    (v, w) = solve(W, N, treasures)
    print('Case %d:\n%d\n%d' % (cnt, v, w))
    cnt += 1

Submission status: Accepted

Solution code:
#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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
cnt = 1
while True:
    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)
    
    av = 0
    aw = 0
    for i in range(W+1):
        if av < dp[i]:
            av = dp[i]
            aw = i

    print("Case {}:".format(cnt))
    print(av)
    print(aw)
    cnt += 1

Submission status: Accepted

Solution code:
MAX = 1005
  
for cno in range(1, 100):
    lim = int(input())
    if lim == 0: break
    print("Case ", cno, ":", sep='')
    N = int(input())
    V = [[0 for j in range(MAX)] for i in range(2)]
    W = [[0 for j in range(MAX)] for i in range(2)]     
    k1, k2 = 0, 1
    for i in range(1, N+1):
        v, w = map(int, input().split(','))
        for j in range(1, w):
            V[k2][j] = V[k1][j]
            W[k2][j] = W[k1][j]
        for j in range(w, lim+1):
            d = j - w
            if V[k1][d] + v >= V[k1][j]:
                V[k2][j] = V[k1][d] + v
                W[k2][j] = W[k1][d] + w
            else:
                V[k2][j] = V[k1][j]
                W[k2][j] = W[k1][j]
        k1, k2 = k2, k1
    print(V[k1][lim], W[k1][lim], sep='\n')

Submission status: Accepted

Solution code:
# AOJ 0042 A Thief
# Python3 2018.6.22 bal4u
 
MAX = 1003
 
for cno in range(1, 100):
    lim = int(input())
    if lim == 0: break
    print("Case ", cno, ":", sep='')
    N = int(input())
    V = [[0 for j in range(MAX)] for i in range(2)]
    W = [[0 for j in range(MAX)] for i in range(2)]     
    k1, k2 = 0, 1
    for i in range(1, N+1):
        v, w = map(int, input().split(','))
        for j in range(1, w):
            V[k2][j] = V[k1][j]
            W[k2][j] = W[k1][j]
        for j in range(w, lim+1):
            d = j - w
            if V[k1][d] + v >= V[k1][j]:
                V[k2][j] = V[k1][d] + v
                W[k2][j] = W[k1][d] + w
            else:
                V[k2][j] = V[k1][j]
                W[k2][j] = W[k1][j]
        k1, k2 = k2, k1
    print(V[k1][lim], W[k1][lim], sep='\n')

Submission status: Accepted

Solution code:
l=1
for W in iter(input,'0'):
 W=int(W)
 D=[0,0]*W
 for p in[0]*int(input()):
  v,w=map(int,input().split(','))
  for i in range(W,w-1,-1):D[i]=max(D[i],D[i-w]+v)
 print(f'Case {l}:\n{D[W]}\n{D.index(D[W])}')
 l+=1

Submission status: Accepted

Solution code:
mininf = -10**8
inf = 10**8
count = 0

while(1):
    count += 1
    W = int(input())
    if W == 0:
        break
    N = int(input())

    dp = [0 for j in range(W+1)]
    for _ in range(N):
        v,w = [int(i) for i in input().split(",")]
        for i in range(w,W+1)[::-1]:
            dp[i] = max(dp[i], dp[i-w]+v)
    value = 0
    weight = 0
    for i in range(W+1):
        if value < dp[i]:
            value = dp[i]
            weight = i

    print("Case {}:".format(count))
    print(value)
    print(weight)

Submission status: Accepted

Solution code:
r,m,I=range,max,input
for lp in r(99):
 W=I()+1
 if W==1:break
 N=I()
 D=[0]*W
 for loop in r(N):
  v,w=map(int,raw_input().split(','))
  for i in r(w,W)[::-1]:D[i]=m(D[i],D[i-w]+v)
 print'Case',str(lp+1)+':'
 print m(D)
 print D.index(m(D))

Submission status: Accepted

Solution code:

# メモ化+非再帰を用いた場合
case_no = 1
while True:
    W = int(input())
    if W == 0:
        break
    N = int(input())
    treasures = [tuple(map(int, input().split(','))) for _ in range(N)]
    
    V = [[0 for w in range(W+1)] for i in range(N+1)]
    weight = [[0 for w in range(W+1)] for i in range(N+1)]
    for i in range(1, N+1):
        for w in range(W+1):
            vi = treasures[i-1][0]
            wi = treasures[i-1][1]
            if wi <= w and vi != 0:
                l = V[i-1][w-wi] + vi
                r = V[i-1][w]
                if l > r:
                    V[i][w] = l
                    weight[i][w] = weight[i-1][w-wi] + wi
                else:
                    V[i][w] = r
                    weight[i][w] = weight[i-1][w]
            else:
                V[i][w] = V[i-1][w]
                weight[i][w] = weight[i-1][w]
    
    sum_value = 0
    sum_weight = 1e100
    for i in range(1, N+1):
        for j in range(W+1):
            if V[i][j] > sum_value or (V[i][j] == sum_value and weight[i][j] < sum_weight):
                sum_value = V[i][j]
                sum_weight = weight[i][j]
    
    print('Case {}:'.format(case_no))
    print(sum_value)
    print(sum_weight if sum_weight != 1e100 else 0)
    case_no += 1

Submission status: Runtime Error

Solution code:
count = 0

while True:
    count += 1
    W = int(input())
    if W == 0:
        break
    N = int(input())
    value = []
    weight = []
    for i in range(N):
        a, b = map(int, input().split())
        value.append(a)
        weight.append(b)
    dp = [[-float("inf") for i in range(W+1)] for j in range(N+1)]
    for i in range(W+1):
        dp[0][i] = 0
        
    for i in range(N):
        for w in range(W+1):
            if w >= weight[i]:
                dp[i+1][w] = max(dp[i][w-weight[i]]+value[i], dp[i][w])
            else:
                dp[i+1][w] = dp[i][w]
    print("Case {0}:\n{1}\n{2}".format(count, dp[N][W], dp[N].index(dp[N][W])))

Submission status: Runtime Error

Solution code:
while True:
    # try:
    case=0
    while True:
        case+=1
        weight=input()
        if weight==0:
            break
        N=input()
        data=[[0 for i in range(2)] for j in range(N)]
        for i in range(N):
            data[i][0],data[i][1]=map(int,raw_input().split(","))
        table=[[-1 for i in range(weight+1)] for j in range(N)]
        for i in range(N):
            table[i][0]=0
        table[0][data[0][1]]=data[0][0]
        for i in range(0,N-1):
            for j in range(weight+1):
                if table[i][j]!=-1 and j+data[i+1][1] <= weight:
                    table[i+1][j+data[i+1][1]]=table[i][j]+data[i+1][0]
        sum=max(table[N-1])
        print "Case "+str(case)+":"
        print sum
        print table[N-1].index(sum)
#    except:
#break

Submission status: Runtime Error

Solution code:
import itertools

count = 0
while True:
	w = int(raw_input())
	if w == 0:
		break
	m = int(raw_input())
	n = [0 for _ in xrange(m)]
	h = [0 for _ in xrange(m)]
	count += 1
	
	for i in xrange(m):
		n[i],h[i] = map(int,raw_input().split(","))
	
	js= []
	for i in xrange(m):
		lis = list(itertools.combinations(n,  m - i))
		for j in lis:
			js.append(sum(j))
	
	jk = []
	for i in xrange(m):
		lis = list(itertools.combinations(h,  m - i))
		for j in lis:
			jk.append(sum(j))
	
	jc = list(filter(lambda x: x < w, jk))
	jc.sort()
	js.sort()
	print "Case " + str(count) + ":"
	print js[len(jc) - 1]
	print jc[len(jc) - 1]