p00042 A Thief
A thief sneaked into a museum with a lot of treasures with only one large furoshiki. There are many things I want to steal, but the weight that the furoshiki can withstand is limited, and if it exceeds this, the furoshiki will tear. Therefore, the thief must consider a combination of treasures that will not break the prepared furoshiki and will be the most valuable.

The weight W that the bath room can withstand, and the value and weight of each treasure in the museum are read, and the total value of the treasure is the maximum when the total value does not exceed W. Create a program that outputs the total weight. However, if there are multiple combinations that maximize the sum of values, the one with the smallest sum of weights will be output.



Input

Given multiple datasets. Each dataset is given in the following format:


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


The first line gives the integer W (W ≤ 1,000), which represents the weight that the furoshiki can bear, and the second line gives the number of treasures N (1 ≤ N ≤ 1,000). The next N lines are given a set of the integer vi (0 ≤ vi ≤ 10,000) representing the value of the i-th treasure and the integer wi (0 ≤ wi ≤ W) representing its weight.

When W is 0, it is the last input. The number of datasets does not exceed 50.

Output

Output as follows for each data set.


Case dataset number:
Sum of the value of the treasure in the furoshiki
Sum of the weight of the treasure at that time


Example

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

Case 1:
220
49
Case 2:
220
49
```python
"""
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()


```