let id x = x

let rec iteri f s t = if s > t then () else begin f s; iteri f (s + 1) t end

let rec read n = if n <= 0 then ([],[])
                 else let x, y = Scanf.scanf "%d,%d\n" (fun x y -> (x, y)) in 
                      let (xs, ys) = read (n - 1) in (x::xs, y::ys)

let solve dp vs ws n w =
  iteri (fun i -> 
         iteri (fun j -> 
                if j >= ws.(i) then dp.(i+1).(j) <- max dp.(i).(j) (dp.(i).(j - ws.(i)) + vs.(i)) 
                else dp.(i+1).(j) <- dp.(i).(j)) 0 w) 0 (n - 1)

let rec min_w dp i j v = 
  if dp.(i).(j) = v then min_w dp i (j - 1) v else j + 1

let _ =
  let cnt = ref 0 in
  try
    while true do
      let w = Scanf.scanf "%d\n" id in
      if w = 0 then 
        raise End_of_file
      else
        let n = Scanf.scanf "%d\n" id in
        let dp = Array.make_matrix (n + 1) (w + 1) 0 in
        let vs', ws' = read n in
        let vs = Array.of_list vs' in
        let ws = Array.of_list ws' in
        solve dp vs ws n w;
        incr cnt;
        Printf.printf "Case %d:\n" !cnt;
        Printf.printf "%d\n" (dp.(n).(w));
        Printf.printf "%d\n" (min_w dp n w dp.(n).(w))
    done
  with
    End_of_file -> ()