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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	static final int MAX_BAG_WEIGHT = 1000;
	static final int MAX_NUM_TREASURES = 1000;
	static final int MAX_VALUE = 10000;
	static final int WEIGHT = 0;
	static final int VALUE = 1;

	public static void main(String[] args){
		try{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int bagWeight = 0;
		int num_treasures = 0;
		int caseNumber = 1;
		Treasure[] treasure;
		Thief thief = new Thief();
		while(true){
			//bagを生成
			bagWeight = Integer.parseInt(br.readLine());
			if(bagWeight == 0 /*|| bagWeight > MAX_BAG_WEIGHT*/) break;
			Bag bag = new Bag(bagWeight);
			
			thief.setBag(bag);
			
			//お宝リストを生成
			num_treasures = Integer.parseInt(br.readLine());
//			if(num_treasures < 1 || num_treasures > MAX_NUM_TREASURES) break;
			treasure = new Treasure[num_treasures];
			for(int i = 0; i < num_treasures; i++){
				String[] inputs = (br.readLine()).split(",");
				int treasureValue = Integer.parseInt(inputs[WEIGHT]);
				int treasureWeight = Integer.parseInt(inputs[VALUE]);
				treasure[i] = new Treasure(treasureWeight, treasureValue);
			}
			
			//動的計画法
			int[] maxValueOfEachWeight = thief.getMaxValue(treasure);
			
			//価値がもっとも高いときの、もっとも軽い重量を出力する
			System.out.println("Case " + caseNumber++ + ":");
			System.out.println(maxValueOfEachWeight[maxValueOfEachWeight.length - 1]);
			System.out.println(thief.getMinWeightWhenMaxValue(maxValueOfEachWeight));
		}
		br.close();
		}catch(IOException e){
			e.printStackTrace();
		}
	}
	static class Bag{
		private int maxWeight;
		public Bag(int maxWeight) {
			this.maxWeight = maxWeight;
		}
		public int getMaxWeight() {
			return this.maxWeight;
		}
	}

	static class Treasure{
		private int weight;
		private int value;
		public Treasure(int weight, int value) {
			this.weight = weight;
			this.value = value;
		}
		public int getValue() {
			return this.value;
		}
		public int getWeight() {
			return this.weight;
		}
	}

	static class Thief{
		private Bag bag;
		public void setBag(Bag bag) {
			this.bag = bag;
		}
		/*TODO ruby実装*/
		public int[] getMaxValue(Treasure[] treasure){
			int[] maxValue = new int[this.bag.getMaxWeight() + 1];	//各バッグ積載可能重量での最大valueを格納する
			//重量が0のとき、treasureはつめないためvalue = 0
			maxValue[0] = 0;			
			//バッグには何もつめられていないため、0で初期化
			Arrays.fill(maxValue, 0);	
			//各treasureについて、バッグ積載可能重量に空きがあり、
			//treasureを追加することでvalueが大きくなるなら追加していく
			for(int i = 0; i < treasure.length; i++){
				int treasureWeight = treasure[i].getWeight();
				int treasureValue = treasure[i].getValue();
				for(int weight = this.bag.getMaxWeight(); weight >= treasureWeight; weight--){
					if(maxValue[weight - treasureWeight] < 0){
						//treasureが詰められない場合は次のアイテムを検討する
						break;
					}
					int tmpValue = maxValue[weight - treasureWeight] + treasureValue;
					maxValue[weight] = Math.max(maxValue[weight], tmpValue);
				}
			}
			return maxValue;
		}
		/*TODO ruby実装*/
		public int getMinWeightWhenMaxValue(int[] maxValueOfEachWeight){
			int minWeight = this.bag.getMaxWeight();
			int maxValue = maxValueOfEachWeight[minWeight];
			for(int weight = this.bag.getMaxWeight(); weight >= 0; weight--){
				if(maxValue > maxValueOfEachWeight[weight]){
					break;
				}
				minWeight = weight;
			}
			return minWeight;
		}
	}
}