Optimal Cake Cutting Game

A rectangular cake of size \( n\times m \) is given. Its vertices are \((0,0)\) (top‐left), \((0,m)\) (top‐right) and \((n,m)\) (bottom‐right). There are \( k \) pieces of chocolate placed on the cake. The \( i\)th chocolate is located at \( (x_i-0.5,y_i-0.5) \). Note that several chocolates may occupy the same position.

The cake is to be cut by two players, Little W and Little M. A knife initially placed at \((0,0)\) is moved in turns; Little W moves first. At any move, if the knife is at \((x,y)\) it can be moved either to \((x,y+1)\) (a right move) or to \((x+1,y)\) (a down move). After a series of moves the knife traces a monotonic path from \((0,0)\) to \((n,m)\) cutting the cake completely into two parts. The part connected to the top–right corner \((0,m)\) is given to Little W, and the part connected to the bottom–left corner is given to Little M.

Both players want to maximize the number of chocolate pieces they receive. Assuming both play optimally, determine how many pieces Little W will get.

The key observation is that any monotonic path from \((0,0)\) to \((n,m)\) uniquely determines a partition of the cake rows. For each row \( i (1 \le i \le n) \), let the value \( p_i \) (with \(1\le p_i\le m+1\)) be defined as the first column such that the cut goes down, so that the entire row \( i \) is partitioned into two parts: columns \( 1,2,\dots, p_i-1 \) go to Little M and columns \( p_i, p_i+1,\dots, m \) go to Little W. Note that \( p_1\le p_2\le \cdots\le p_n \).

If we define, for each row \( i \) and any column \( c \),

[ R(i,c)=\sum_{j=c}^{m} A(i,j), ]

where \(A(i,j)\) is the number of chocolate pieces in cell \( (i,j) \) (with chocolate pieces placed at \((x-0.5, y-0.5)\) assigned to cell \( (x,y) \) for \(1\le x\le n,\ 1\le y\le m\)), then Little W's total chocolate count is \(\sum_{i=1}^{n} R(i,p_i)\) and the total chocolate count is \(T=\sum_{i=1}^{n} R(i,1)\).

The game is zero–sum since Little M gets the remaining \( T-\sum_{i=1}^{n} R(i,p_i) \) pieces. By a standard argument this game can be solved by dynamic programming with a minimax formulation. Define the game state by \( (r,j) \), where \( r \) is the number of rows whose cut has been determined and \( j \) is the current column position of the knife. A right move (to \((r,j+1)\)) has no immediate reward, while a down move (to \((r+1,j)\)) finalizes the cut for row \( r+1 \) and yields an immediate reward of \( R(r+1,j+1) \) for Little W (or \( -R(r+1,j+1) \) if Little M makes the move). The turns alternate starting with Little W. Let \( f(r,j) \) denote the game value (the difference between Little W's and Little M's final chocolate counts) from state \((r,j)\). Then the recurrence is:

[ f(r,j)= \begin{cases} 0, & \text{if } r=n,\ \max\Big{ f(r,j+1),; R(r+1,j+1)+f(r+1,j) \Big}, & \text{if } (r+j) \text{ is even (W's turn) and } j<m,\ R(r+1,j+1)+f(r+1,j), & \text{if } (r+j) \text{ is even and } j=m,\ \min\Big{ f(r,j+1),; -R(r+1,j+1)+f(r+1,j) \Big}, & \text{if } (r+j) \text{ is odd (M's turn) and } j<m,\ -R(r+1,j+1)+f(r+1,j), & \text{if } (r+j) \text{ is odd and } j=m. \end{cases} ]

Finally, Little W's result is \(\displaystyle \frac{T+f(0,0)}{2}\).

Input Format:

• The first line contains three integers \( n\), \( m\), and \( k\) (the dimensions of the cake and the number of chocolates).
• The next \( k \) lines each contain two integers \( x_i \) and \( y_i \), indicating that a chocolate is placed in the cell \( (x_i, y_i) \).

Output Format:

• Output a single integer, the number of chocolate pieces Little W will get if both players play optimally.

inputFormat

First line: three space‐separated integers \( n, m, k \).
Next \( k \) lines: each contains two space–separated integers \( x \) and \( y \) (\(1\le x\le n,\ 1\le y\le m\)).

outputFormat

A single integer representing the number of chocolate pieces Little W obtains under optimal play.

sample

1 1 1
1 1

1

</p>