Let's play a fun game. The game is played in a N x N size grid. There are M players in this game. Each have their own initial check point (x, y) from where they start their journey. Each player has to go to exactly D destinations to complete their quest. When one player arrives at one destination, he immediately goes back to his initial position from where he started his journey. Then he will start his journey for the next destination. The game is over when all of the players have completed their quest.
Each player can go from cell (x, y) to any of four cells (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1). To make this game interesting, there are K portals located in different places in grid. Going into a portal means a player can immediately go from one cell to other. And a portal is a two way path from cell1 to cell2, meaning, a player can move from cell1 to cell2 or vice versa. Player can decide whether he wants to use the portal or not. Going from one cell to other costs 1 energy point. Each player will go to each destination from their initial cell using minimum energy points. You have to find out the total number of energy points for all the players combined after finishing the game.
Travelling using portal doesn't need any energy point. Also keep in mind that there can be multiple portal in same cell.
Input
First line of input contains an integer N(1 <= N <= 1000) denoting the size of the N x N grid. Next line will contain three integers M(1 <= M <= 1000000), D(1 <= D <= 10) & K(0 <= K <= 1000) denoting the number of players, destinations & portals.
Next M lines will contain two integers mxi & myi(0 <= mx, my < N) denoting the position of mi th player.
Next D lines will contain two integers dxi & dyi(0 <= dx, dy < N) denoting the destination position of di.
Next K lines will contain four integers kxi, kyi, kxj & kyj(0 <= kxi, kyi, kxj & kyj < N) where (kxi, kyi) denotes the ki th portal's position and (kxj, kyj) denotes the cell position where ki portal will teleport one player and vice versa.
Output
Print one integer in a single line denoting the number of total energy points used by each player after the game is finished.
Sample
| Input | Output |
|---|---|
4 2 2 1 0 0 1 0 0 3 3 2 0 1 3 3 | 12 |
