404189: GYM101446 C Arcade Game

You are playing an oldschool arcade game. The point of the game is to dodge enemy bullets.

The screen is n cells wide and 10⁶ cells high. The cells are indexed by their column index x and row index y; indices are 1-based. You control a spaceship which has a shape of a rectangle one cell wide and H cell high. Your spaceship's bottom edge is aligned with the bottom edge of the screen, that is, your ship always occupies cells (x, 1), (x, 2), ..., (x, H) for your current x.

All l bullets that you have to dodge are already on the screen, i-th of them is located at the center of the cell (x_i, y_i). Each bullet occupies one cell. The game consists of m rounds, each round proceeds as follows:

• First, you can move your ship one cell to the left or to the right; you are also free to stay still. You cannot move outside the screen.
• Next, all bullets move down one cell, except for the bullets in the bottom row that instead disappear.

If at any point of time, any cell of your ship contains a bullet, you immediately lose. If you stay alive after the m-th round concludes, you win.

You have played k games. In i-th of these games, the starting column of your ship was a_i. You are now wondering: how many of these games you could have won if you played optimally?

The first line of input contains five integers n, m, k, l, and h (1 ≤ n, k, l, h ≤ 10⁶, 1 ≤ m ≤ 10³).

The second line contains k space-separated integers a_i: the initial positions of the spaceship in each of your games.

Next l lines describe the positions of bullets. Each of these lines contains two integers x_i and y_i: column and row index of the respective bullet (1 ≤ x_i ≤ n, H + 1 ≤ y_i ≤ 10⁶).

Print one integer: the answer to the problem.

3 3 2 2 2
1 2
1 3
2 3

1

6 10 7 7 3
1 2 2 3 4 5 6
6 10
2 4
2 6
3 5
4 4
5 6
6 10

6