Şehmettin is a Computer Engineering student who plays GemTD (a mediocre-at-best tower defense game) instead of studying. He decided to get the best possible score at least since he was playing this boring game instead of fulfilling his responsibilities.

GemTD works like this:

• The game is played on a \(\mathbf{N\times N}\) grid.
• There are 5 checkpoints in total. The enemy spawns from the starting checkpoint, passes by 3 different check-points in the given order, and leave the grid from the last checkpoint.
• The Enemy moves through portals to teleport from one cell to another. (The enemy can only use portals to travel between cells)
• There can be at most \(\mathbf{N}\) portals from one cell. Using a portal, costs resources (for the enemy).
• The enemy wants to go through these cells with the lowest cost possible and will find the path to do so.
• The player chooses a rectangle inside the grid to bombard. For every cell in the bombardment area:
  • If the enemy does not choose to go through a cell, the bombardment of that cell will cost the player \(\mathbf{M}\) points (\(\mathbf{M}\) is a negative integer).
  • If the enemy chooses to go through a cell \(\mathbf{X}\) times the bombardment of that cell will award the player \(\mathbf{X \times K}\) points.

Help Şehmettin get away from this disgusting game by helping him get the maximum number of points possible.

• It is guaranteed that there is exactly one shortest path between subsequent check-points.
• It is guaranteed that the coordinates of all checkpoints are different.

Input

The first line contains 4 integers \(\mathbf{N}\), \(\mathbf{P}\), \(\mathbf{M}\), and \(\mathbf{K}\). Which respectively denote grid's dimensions, number of portals, cost of bombarding an unpassed cell, profit of bombarding a passed cell (multiplies with each pass):

• \(3 \leq \mathbf{N} \leq 100\)
• \(4 \leq \mathbf{P} \leq \mathbf{N^3}\)
• \(-100 \leq \mathbf{M} \leq -1\)
• \(1 \leq\mathbf{K} \leq 100\)

Next 5 lines each contain 2 integers \(\mathbf{x_i}\) and \(\mathbf{y_i}\). \(\mathbf{x_i}\) and \(\mathbf{y_i}\) are the coordinates of checkpoints [starting checkpoint and 4 remaining checkpoints]:

• \(1\leq \mathbf{x_i}, \mathbf{y_i} \leq \mathbf{N}\)

Next \(\mathbf{P}\) lines each contains 5 integers \(\mathbf{x1_i}\), \(\mathbf{y1_i}\), \(\mathbf{x2_i}\), \(\mathbf{y2_i}\) and \(\mathbf{w}\). \(\mathbf{x_i}\)s and \(\mathbf{y_i}\)s are the coordinates of both ends of the portal and \(\mathbf{w}\) is the cost of transporting through the portal:

• \(1\leq \mathbf{x1_i}, \mathbf{y1_i}, \mathbf{x2_i}, \mathbf{y2_i} \leq \mathbf{N}\)
• \(1\leq\mathbf{W}\leq 10000\)

Output

Print the maximum number of points Şehmettin can get.

Example

Input 1:

3 5 -7 3
1 1
1 3
3 3
3 1
2 2
1 1 1 3 7
3 3 1 3 8
3 3 3 1 3
3 1 1 2 13
2 2 1 2 15

Output 1:

9

Input 2:

5 10 -3 7
1 1
1 5
5 5
5 1
2 2
1 1 3 5 5
3 5 1 5 4
1 5 5 5 1
5 5 5 2 3
5 2 5 1 1000
5 1 1 1 300
1 1 2 2 10000
5 5 4 4 4
4 4 2 1 10
4 4 3 1 10

Output 2:

29

Explanation

Input 1

• The shortest path from 1 1 to 1 3 uses one portal: [1 1 1 3 7]
• The shortest path from 1 3 to 3 3 uses one portal: [3 3 1 3 8]
• The shortest path from 3 3 to 3 1 uses one portal: [3 1 3 3 15]
• The shortest path from 3 1 to 2 2 uses two portals: [3 1 1 2 13, 2 2 1 2 15]

If the player bombards the rectangle that includes the cells 1 1, 1 2, 1 3 9 points would be gained which is the highest possible.