Coins on the Board#7803
You have a chessboard with dimensions N \times M. The rows are numbered from to , and the columns from to . Some cells on this board already contain coins. In one move, you can select two empty cells (r_1, c_1) and (r_2, c_2) such that r_1 - r_2 = DR and c_1 - c_2 = DC, and place one coin in each of these cells. You can perform this action as many times as you like.
Your task is to determine the maximum number of additional coins you can place on the board, not counting the coins that are already there.
The first line contains five integers , , , , and , separated by spaces. Here, represents the number of cells that initially contain coins. Each of the following lines contains two integers r_i and c_i, separated by a space, indicating the row and column of the -th cell with a coin.
Output the maximum number of additional coins you can place on the board.
Constraints:
1 \le N, M \le 10^9
1 \le DR, DC \le 10^9
0 \le K \le 10^5
1 \le r_j \le N
1 \le c_j \le M
All cells (r_j, c_j) are distinct.
Example 1
Example 2
In the first example, you have an empty 3 \times 3 board with DR = DC = 1. In the first move, you can select the pair of cells and . In the second move, you can choose and . In the third move, you can select and .