c =0

while True:

    W = eval(input())

    if W==0: break

    dt = [0]*1001

    c +=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 = 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)
def f():

    p,w = eval(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 = eval(input())

    if W==0: break

    R = list(range(W+1))[::-1]

    dt = [0]*1001

    c += 1

    N = eval(input())

    for i in range(N): f()

    m = max(dt)

    n = dt.index(m)

    print("Case {}:\n{}\n{}".format(c,m,n))
c = 0
while True:
    W = eval(input())
    if W == 0:
        break
    dt = [0] * 1001
    c += 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 = 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)

def f():
    p, w = eval(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 = eval(input())
    if W == 0:
        break
    R = list(range(W + 1))[::-1]
    dt = [0] * 1001
    c += 1
    N = eval(input())
    for i in range(N):
        f()
    m = max(dt)
    n = dt.index(m)
    print("Case {}:\n{}\n{}".format(c, m, n))

+def f(): +    p, w = eval(input()) +    for w0 in R[w:]: +        w1, p1 = w0 + w, dt[w0] + p +        if dt[w1] < p1: +            dt[w1] = p1 +    return + + -while True: +while 1: +    R = list(range(W + 1))[::-1] -    m = 0 -    n = 0 -        p, w = eval(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 +        f() -    print("Case {}:".format(c)) -    print(m) -    print(n) +    print("Case {}:\n{}\n{}".format(c, m, n))