#include <iostream>
#include <map>
#include <algorithm>
#include <cstdint>

typedef std::uint32_t WeightType;
typedef std::uint32_t ValueType;
typedef std::map<WeightType, ValueType> DPMap;

class LessSecond {
public:
	bool operator()(DPMap::value_type lhs, DPMap::value_type rhs) const
	{ return lhs.second < rhs.second; }
};

int main()
{
	std::uint32_t count = 0;
	WeightType W;
	for (std::cin >> W; W != 0; std::cin >> W) {
		DPMap dp_map;
		dp_map.insert(DPMap::value_type(0u, 0u));

		std::uint16_t n;
		std::cin >> n;

		for (std::uint32_t i = 0; i < n; ++i) {
			ValueType value;
			WeightType weight;
			(std::cin >> value).ignore() >> weight;

			for (auto it = dp_map.rbegin(); it != dp_map.rend(); ++it) {
				WeightType const new_weight = it->first + weight;
				ValueType const new_value = it->second + value;
				if (new_weight <= W) {
					auto insert_pos = dp_map.lower_bound(new_weight);
					if (insert_pos != end(dp_map) and
							not dp_map.key_comp()(new_weight, insert_pos->first)) {
						insert_pos->second = std::max(insert_pos->second, new_value);
					}
					else {
						dp_map.insert(insert_pos, DPMap::value_type(new_weight, new_value));
					}
				}
			}
		}

		auto max_pos = std::max_element(begin(dp_map), end(dp_map), LessSecond());
		std::cout << "Case " << ++count << ":\n"
				  << max_pos->second << "\n"
				  << max_pos->first << std::endl;
	}
}