"""

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(eval(input()))

    if not w:

      break

  

    case += 1

  

    n = int(eval(input()))

  

    vlst = [0]

    wlst = [0]

  

    for _ in range(n):

      vin, win = list(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()



"""

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(eval(input()))

    if not w:

      break

  

    case += 1

  

    n = int(eval(input()))

  

    dp = [0 for _ in range(w + 1)]

    

    for i in range(1, n + 1):

      vi, wi = list(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()



"""
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(eval(input()))
        if not w:
            break
        case += 1
        n = int(eval(input()))
        vlst = [0]
        wlst = [0]
        for _ in range(n):
            vin, win = list(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()

"""
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(eval(input()))
        if not w:
            break
        case += 1
        n = int(eval(input()))
        dp = [0 for _ in range(w + 1)]
        for i in range(1, n + 1):
            vi, wi = list(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()

-wi = wlst[i]...i個目の重さ -vi = vlst[i]...i個目の価値 +wi...i個目の重さ +vi...i個目の価値 -or +1次元 -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) +dp[j] = max(dp[j], dp[j - wi] + vi)  (wi <= j <= w) +wi <= j <= wについて更新(j < wiについては変化が無いため更新不要) +前から更新すると更新した結果を使って更新してしまうため後ろから更新 -        vlst = [0] -        wlst = [0] -        for _ in range(n): -            vin, win = list(map(int, input().split(","))) -            vlst.append(vin) -            wlst.append(win) -            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]) +            vi, wi = list(map(int, input().split(","))) +            for j in range(w, wi - 1, -1): +                dp[j] = max(dp[j], dp[j - wi] + vi)