Woburn Challenge 1996

Given is an ~M~ by ~N~ grid and on each square of the grid there may or may not be an apple on it. Let ~A~ be the bottom left square and ~B~ be the upper right square of the grid. Find the path from ~A~ to ~B~ (shown below) going up and right only that passes through the most number of squares with apples in them. For this path output the number of apples on it.

For example, here is a 4 by 4 grid:

    .a.a <-B
    ..aa
    a.a.
A-> ....

Each square can have at most one apple (this includes squares ~A~ and ~B~).

Input Specification

Your program should read in the size of the grid, ~M~ and ~N~, where ~1 \le M, N \le 100~. The locations of the apples where ~A~ is at ~(1, 1)~ and ~B~ is at ~(M, N)~. Inputs will end with 0 0 and have the same format as the one below. In our example, the input would be

4 4
2 1
2 3
3 3
3 4
4 2
4 4
0 0

Output Specification

Give the number of apples on the path with the most number of them. In this case

5