count =0

while True:

    W = eval(input())

    if (W==0): break

    work={0:0}

    count +=1

    N = eval(input())

    for i in range(N):

        p,w = eval(input())

        for w0 in sorted(list(work.keys()),reverse=True):

            w1 = w0+w

            p1 = work[w0]+p

            if w1>W or (w1 in work and work[w1]>=p1): continue

            else: work[w1] = p1



    m = max(work.values())

    tmp = list(work.values()).index(m)

    n = list(work.keys())[tmp]

    print("Case %d:" %(count))

    print(m)

    print(n)
count =0

while True:

    W = eval(input())

    if W==0: break

    work = [0]*1001

    count +=1

    N = eval(input())

    m = 0

    n = 0

    for i in range(N):

        p,w = eval(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)
count = 0
while True:
    W = eval(input())
    if W == 0:
        break
    work = {0: 0}
    count += 1
    N = eval(input())
    for i in range(N):
        p, w = eval(input())
        for w0 in sorted(list(work.keys()), reverse=True):
            w1 = w0 + w
            p1 = work[w0] + p
            if w1 > W or (w1 in work and work[w1] >= p1):
                continue
            else:
                work[w1] = p1
    m = max(work.values())
    tmp = list(work.values()).index(m)
    n = list(work.keys())[tmp]
    print("Case %d:" % (count))
    print(m)
    print(n)

count = 0
while True:
    W = eval(input())
    if W == 0:
        break
    work = [0] * 1001
    count += 1
    N = eval(input())
    m = 0
    n = 0
    for i in range(N):
        p, w = eval(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)

-    work = {0: 0} +    work = [0] * 1001 +    m = 0 +    n = 0 -        for w0 in sorted(list(work.keys()), reverse=True): +        for w0 in range(W + 1)[::-1]: +            p0 = work[w0] +            if w0 > 0 and p0 == 0: +                continue -            p1 = work[w0] + p -            if w1 > W or (w1 in work and work[w1] >= p1): -                continue -            else: +            p1 = p0 + p +            if w1 <= W and work[w1] < p1: -    m = max(work.values()) -    tmp = list(work.values()).index(m) -    n = list(work.keys())[tmp] -    print("Case %d:" % (count)) +                if m < p1: +                    m = p1 +    n = work.index(m) +    print("Case {}:".format(count))