영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
Alexander likes water. Therefore, it's no surprise that he is fond of rushing water. This might explain why he wants to create his own waterfall. Just imagine, water cascading endlessly!
He has found a cliff face that he believes will make the perfect waterfall after he adds some water. The cliff face can be modeled as an R × C grid, where N cells have an outcropping cliff. The rows are numbered from 0 to R-1 from bottom to top, and the columns are numbered from 0 to C-1 from left to right. At columns -1 and C there is a wall that water cannot pass through. Alexander plans to pour water from above so that it flows down in K columns.
The water spreads in the grid according to the following rules: if the cell below the water is empty, it spreads there. If there is a cliff in the way, it instead spreads to the right and left. If there is a cliff in the way to the right or left, it does not spread in that direction. This also applies to the water being poured from above, i.e., if water is poured into column i and the top row has a cliff in column i, it is as if water is also being poured from above in columns i - 1 and i + 1, provided those columns are within the grid.
However, Alexander does not want to cause a flood because then all the water will stand still in the end. Water that stands still is, of course, less exciting than rushing water. Therefore, he wants your help to write a program that calculates how many columns have water in them in the bottom row of the grid.
(그림은 원문 저장소에서 볼 수 있습니다)
Figure 1: An illustration of the flow in samples 1 and 2. The red frame marks the end of the cliff face.
Input
The first line contains two integers R, C (2 ≤ R ≤ 10^9, 1 ≤ C ≤ 10^9), the number of rows and columns that make up the mountain.
The second line contains two integers K, N (1 ≤ K, N ≤ 10^5), the number of columns with water and the number of cliffs protruding from the mountain.
Following this are K lines, where the ith line contains the integer V_i (0 ≤ V_i ≤ C-1), indicating that water flows down along column V_i from above the grid. It is guaranteed that all V_i are unique.
Afterward, there are N lines where each line i contains two integers A_i (1 ≤ A_i ≤ R-1) and B_i (0 ≤ B_i ≤ C-1), representing the row and column where the ith cliff is located. These positions are also unique.
Output
Print an integer: the number of columns that contain water in the bottom row of the grid.
Scoring
Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 20 | R · C ≤ 1000 |
| 2 | 30 | Cliffs can't touch each other diagonally, horizontally or vertically. |
| 3 | 20 | Cliffs can't touch each other diagonally. |
| 4 | 30 | No additional constraints. |
예제
예제 1
8 6 3 4 1 4 5 1 3 2 2 5 1 5 5
3
예제 2
8 6 1 8 3 2 1 1 2 2 3 5 2 5 3 5 4 5 5 6 5
1
예제 3
5 4 1 3 3 1 1 2 2 3 3
1