Minimum Fatigue in Soccer Practice

This problem is adapted from JOI 2017 Final T4 "Soccer".

You are the manager of a renowned soccer club in the JOI League. The club has N players numbered from 1 to N. The soccer field is a rectangle with a width of W meters (east–west) and height of H meters (north–south). We set up a coordinate system such that if from a point you move i meters to the north and j meters to the west to exactly reach the northwest corner, the point is represented by the coordinates (i, j).

After training, you need to recover the practice soccer ball. Initially, every player is on the field. Player 1 has the ball at his feet and is located at (S₁, T₁). You are standing with player N at (S_N, T_N), and you will recover the ball once the ball is passed to the position (S_N, T_N).

You may instruct the players to perform operations. Note that some operations increase a player’s fatigue. A player cannot perform more than one operation at a time. There are two groups of operations:

• For the player currently controlling the ball:
  • Dribble: Move 1 meter in one of the four cardinal directions (north, south, east, or west) while keeping the ball. The fatigue increases by C.
  • Kick: Choose one of the four cardinal directions and a positive integer p. The player kicks the ball exactly p meters in that direction. It is assumed that while the ball is rolling, it can pass through other players. The player does not move and loses control of the ball. The fatigue increases by A \(\times\) p + B (formula in LaTeX: \(A\times p + B\)).
  • Stop Control: The player drops his control without changing his fatigue.
• For players not controlling the ball:
  • Move: Move 1 meter in one of the four cardinal directions; the fatigue increases by C.
  • Take Control: If the ball is at the player’s position and no other player is controlling the ball, the player may take control with no additional fatigue.

Players (and the ball) may run out of the field and multiple players can be at the same location. While more complicated strategies involving passing between players are allowed, one valid strategy is simply to have the player with control (player 1 initially) dribble the ball all the way to (S_N, T_N) (where you are waiting with player N).

The dribble action moves the ball 1 meter per operation with a fatigue cost of C per meter, and the kick action moves the ball in one cardinal direction by any positive integer distance with a fatigue cost of \(A \times p+B\). Notice that a kick can only move the ball strictly north, south, east, or west. Therefore, if the initial ball position is (S₁, T₁) and the target position is (S_N, T_N), letting \(d_v=|S_1-S_N|\) and \(d_h=|T_1-T_N|\), you may separately move the ball vertically and horizontally. For each dimension, you can choose either to dribble at a cost of C per meter, or to kick for the whole distance at a cost of \(A\times d+B\) if \(d>0\) (and cost 0 if \(d=0\)).

Your task is to compute the minimum total fatigue increase over all players required to pass the ball to (S_N, T_N). Formally, the answer is given by:

[ \min(d_v \times C,; [d_v>0]; A\times d_v+B) ; + ; \min(d_h \times C,; [d_h>0] ; A\times d_h+B), ]

where \([d>0]\) is 0 if \(d=0\) and considered when \(d>0\).

Input Constraints and Notes:

• The first line of input contains six integers: N, W, H, A, B, and C.
• Then N lines follow. The i-th line contains two integers S_i and T_i, the initial position of player i.
• You may assume that all input values are integers and that a solution always exists.

Output: Output the minimum total fatigue increase.

inputFormat

The first line contains six space‐separated integers: N, W, H, A, B, and C.

Each of the next N lines contains two integers S_i and T_i (1 ≤ i ≤ N) separated by a space.

Note: Player 1 starts with the ball, and the target is the position of player N.

outputFormat

Output a single integer: the minimum total fatigue increase required.

sample

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

11