A Worthy Finale
Time limit4sMemory limit1024 MB
Find the most black pieces a single white piece can capture in one turn on a huge sparse board, changing capture direction at most twice.
Problem
Hulk and Thanos have decided that there have been enough fights for one day, so they agree to play checkers to settle who is stronger. They play by special rules.
- The board has size . Rows are numbered from 1 to from bottom to top, and columns are numbered from 1 to from left to right.
- Cells whose row and column numbers have the same parity are black. The rest are white.
- Some black cells hold white or black pieces. No cell holds more than one piece.
- Players alternate turns. On a turn, a player either does nothing or moves one piece of their own color: Hulk moves white pieces, and Thanos moves black pieces.
- When a player moves a piece, it makes a sequence of captures. Suppose the piece is on cell , the diagonally adjacent cell holds an opponent's piece, and the next cell in the same direction is empty. Then the player may capture the piece on by moving the piece from to . The jumped piece is removed, so becomes empty. If the piece can capture another opponent piece after a capture, the player may keep capturing with it for as long as they like.
- There is one extra rule: during a single turn, a piece may change its capture direction at most two times. In the figure below, the white piece cannot capture either of the two crowned pieces during its turn. To take the left one, it would have to jump off the board. To take the right one, it would need to change direction a third time. (The first two direction changes happen on the highlighted cells.)

After several moves, Hulk has only one piece left, but he does not plan to give up. Help him capture as many of Thanos's black pieces as possible in one turn.
Input
The first line contains three integers , , and : the height and width of the board, and the number of black pieces ().
The second line contains two integers and , the row and column of the white piece (, ).
Each of the next lines contains two integers and , the row and column of the -th black piece (, ).
It is guaranteed that no two pieces share coordinates. It is also guaranteed that all pieces are on black cells.
Output
Output one integer: the maximum number of black pieces that Hulk's white piece can capture in one turn, following the rules above.