Nut Bowling

This problem is based on a mini‐game inspired by Plants vs. Zombies. In this game, there are N lanes (with N being even) numbered from 1 to N from top to bottom. Each lane is divided into several cells (columns). There are M zombies in the yard; each zombie occupies a cell and its position never changes. The game is played in K rounds.

At the beginning of each round, you choose one lane in which to roll a nut. The nut is thrown from the left wall and rolls horizontally (from left to right) along the chosen lane until it hits the first zombie. When the nut makes its first collision at cell \( (r, c) \), it kills one zombie in that cell (if there are multiple zombies there, only one dies) and then starts rolling diagonally at a 45° angle toward the center of the yard. Specifically, if \( r \leq N/2 \) (i.e. the lane is in the top half), after the collision the nut travels in the right–down direction (i.e. from \( (r, c) \) to \( (r+1, c+1) \)); otherwise (if \( r > N/2 \)), it travels in the right–up direction (i.e. from \( (r, c) \) to \( (r-1, c+1) \)).

While rolling diagonally, the nut continues cell by cell. Before entering a new cell, if the nut would go out of bounds (i.e. if the next row would be 0 or \( N+1 \)) it bounces off the wall; bouncing means that the vertical component of its movement is reversed (right–up becomes right–down and vice versa). In addition, if the nut enters a cell containing at least one zombie, it kills one zombie in that cell and immediately bounces (the vertical direction is reversed) before continuing.

The round ends when the nut can no longer hit any zombies. In other words, if the current cell’s column is not less than the maximum column index of any remaining zombie, then no further collisions will occur and the round finishes.

At the start of every round, with the current distribution of zombies, you must simulate the outcome for every lane. You choose the lane that would kill the maximum number of zombies if a nut was thrown along it; if there are ties, choose the lane with the smallest index. Then, you execute the nut’s path on the actual zombie distribution (removing zombies as they are hit) and add the number of zombies killed in that round to your total score. The game lasts for K rounds (or may effectively stop early if no nut can hit any zombie).

Note: Positions of zombies are given as \( (r,c) \) where \( 1 \le r \le N \) and \( c \ge 1 \). The initial horizontal movement is along the chosen lane from the left wall (column 0) until the first zombie is encountered. All formulas should be read in \( \LaTeX \) format.

inputFormat

The first line contains three integers \(N\), \(M\), and \(K\) denoting the number of lanes, the number of zombies, and the number of rounds respectively. \(N\) is guaranteed to be even.

The following \(M\) lines each contain two integers \(r\) and \(c\) indicating the lane number and column position of a zombie. Note that multiple zombies may be located in the same cell.

\(1 \le r \le N, \; c \ge 1\).

outputFormat

Output a single integer representing the total number of zombies killed after performing the strategy for up to \(K\) rounds.

sample

4 4 3
1 2
2 3
3 4
4 5

4