import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    for (case in 1..50) {
        val W = sc.nextInt()
        if (W == 0) break
        val N = sc.nextInt()
        val a = Array(N, { sc.next().split(",").map { Integer.parseInt(it) } })
        val dp = Array(W+1, { 0 })
        dp[0] = 0
        for ((item_v, item_w) in a) {
            for (to_w in W downTo item_w) {
                dp[to_w] = Math.max(dp[to_w], dp[to_w-item_w]+item_v)
            }
        }
        val ans = dp.max()!!
        val index = dp.indexOf(ans)
        println("Case $case:")
        println(ans)
        println(index)
    }
}
