Maximizing Treasure Collection in a Grid

You are given a grid of size \( n \times m \) with certain cells containing treasures. You start at the top-left cell \( (1,1) \) and must reach the bottom-right cell \( (n,m) \). You can only move either right or down at each step.

Your task is to determine the maximum number of treasures that can be collected along an optimal path. A cell with a treasure contributes \( 1 \) to your total count if visited. The treasures are given as a list of coordinates. Use dynamic programming to solve this problem efficiently.

The recurrence relation for dynamic programming is:

[ dp[i][j] = \max(dp[i-1][j], dp[i][j-1]) + grid[i][j] ]

with the proper initialization of the first row and first column.

inputFormat

The first line of input contains three integers \( n \), \( m \), and \( q \), where \( n \) is the number of rows and \( m \) is the number of columns in the grid, and \( q \) is the number of treasure cells.

The following \( q \) lines each contain two integers \( x \) and \( y \), representing the row and column indices of a cell containing a treasure.

outputFormat

Output a single integer representing the maximum number of treasures that can be collected when moving optimally from \( (1,1) \) to \( (n,m) \).

## sample

3 3 3
1 2
2 2
3 3

3

</p>