Problem Description

Takahashi is planning to move to a certain room.

The room is composed of square cells arranged in $ R $ rows and $ C $ columns. We will call the cell at the $i\ (1\ ≦\ i\ ≦\ R)$ row and $j\ (1\ ≦\ j\ ≦\ C)$ column as cell $ (i,j) $.

There are a total of $ N $ candies distributed across these cells. Each candy is numbered from $ 1 $ to $ N $, and candy $i\ (1\ ≦\ i\ ≦\ N)$ is located at cell $ (r_i,c_i) $. No two candies are located on the same cell.

Takahashi will move to any one cell in the room. After moving, Takahashi will collect candies as follows:

• First, he collects all candies located in the same row as the cell he is in.
• Then, he collects all candies located in the same column as the cell he is in.

Takahashi will not perform any other actions.

Takahashi wants to collect exactly $ K $ candies. Determine the total number of cells he can move to such that he collects exactly $ K $ candies.

Input Format

The input is given from the standard input in the following format:

$ R $ $ C $ $ K $ $ N $ $ r_1 $ $ c_1 $ $ r_2 $ $ c_2 $ : $ r_N $ $ c_N $

• The first line contains three integers $R\ (1\ ≦\ R\ ≦\ 100,000)$, $C\ (1\ ≦\ C\ ≦\ 100,000)$, and $K\ (1\ ≦\ K\ ≦\ 100,000)$ separated by spaces. This indicates that the room consists of $ R $ rows and $ C $ columns of square cells. $ K $ is the number of candies Takahashi wants to collect.
• The second line contains an integer $N\ (K\ ≦\ N\ ≦\ 100,000)$, representing the total number of candies.
• The next $ N $ lines contain information about the candies. The $i\ (1\ ≦\ i\ ≦\ N)$ line contains two integers $r_i\ (1\ ≦\ r_i\ ≦\ R)$ and $c_i\ (1\ ≦\ c_i\ ≦\ C)$ separated by spaces. This indicates that candy $ i $ is located at cell $ (r_i,c_i) $.
• For $ i≠j $, $ (r_i,c_i)≠(r_j,c_j) $.

Output Format

Output the total number of cells Takahashi can move to such that he collects exactly $ K $ candies in one line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

3 5 3
5
1 2
2 1
2 5
3 2
3 5

Sample Output #1

5

Sample Input #2

7 3 1
4
3 2
3 3
4 2
4 3

Sample Output #2

0

Sample Input #3

5 5 2
5
1 1
2 2
3 3
4 4
5 5

Sample Output #3

20

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset where $R\ ≦\ 50$, $C\ ≦\ 50$, and $N\ ≦\ 50$, you will be awarded $ 30 $ points.
• If you solve the dataset without additional constraints, you will be awarded an additional $ 70 $ points.

Sample Explanation 1

For example, consider if Takahashi moves to cell $ (3,2) $.

• Candy $ 1 $ is at cell $ (1,2) $. Since this cell is in the same column as cell $ (3,2) $, Takahashi collects candy $ 1 $.
• Candy $ 2 $ is at cell $ (2,1) $. This cell is neither in the same row nor the same column as cell $ (3,2) $, so Takahashi does not collect candy $ 2 $.
• Candy $ 3 $ is at cell $ (2,5) $. This cell is neither in the same row nor the same column as cell $ (3,2) $, so Takahashi does not collect candy $ 3 $.
• Candy $ 4 $ is at cell $ (3,2) $. Since this cell is the same as cell $ (3,2) $, Takahashi collects candy $ 4 $.
• Candy $ 5 $ is at cell $ (3,5) $. Since this cell is in the same row as cell $ (3,2) $, Takahashi collects candy $ 5 $.

Thus, Takahashi collects exactly $ 3 $ candies: $ 1 $, $ 4 $, and $ 5 $. Therefore, cell $ (3,2) $ is a valid move. There are also other cells like $ (1,5) $, $ (2,5) $, $ (3,1) $, and $ (3,5) $ that satisfy the condition, so the answer is $ 5 $.

Sample Explanation 2

No matter where Takahashi moves, he cannot collect exactly $ 1 $ candy.

见题面 Input 部分

见题面 Output 部分