Under construction

Still being built. Things may change

A Worthy Finale

Time limit4sMemory limit1024 MB

Summary
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.
Level

Hard8 of 10

Topics
DFS, Graph, Hash map
Solved
No attempts yet

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 h×wh \times w. Rows are numbered from 1 to hh from bottom to top, and columns are numbered from 1 to ww 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 AA, the diagonally adjacent cell BB holds an opponent's piece, and the next cell CC in the same direction is empty. Then the player may capture the piece on BB by moving the piece from AA to CC. The jumped piece is removed, so BB 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 hh, ww, and nn: the height and width of the board, and the number of black pieces (1≤h,w,n≤250 0001 \le h, w, n \le 250\,000).

The second line contains two integers pp and qq, the row and column of the white piece (1≤p≤h1 \le p \le h, 1≤q≤w1 \le q \le w).

Each of the next nn lines contains two integers rir_i and sis_i, the row and column of the ii-th black piece (1≤ri≤h1 \le r_i \le h, 1≤si≤w1 \le s_i \le w).

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.

Examples1

  1. Example 1

    Input
    12 8 8
    2 2
    9 1
    9 3
    11 3
    3 3
    5 5
    11 5
    9 7
    7 7
    
    Expected output
    6