Ladder Game

There is a ladder used for a ladder game. It has N vertical lines and M horizontal lines. The vertical lines are numbered 1, 2, ..., N from left to right, and the horizontal lines are numbered 1, 2, ..., M from top to bottom. No two horizontal lines are at the same height.

A traveler starts at position a at the top and moves downward along the ladder. Whenever the traveler meets a horizontal line, the traveler moves to the adjacent vertical line connected by that horizontal line.

You may change the ladder. Removing one existing horizontal line costs X, and drawing one new horizontal line costs Y. A new horizontal line connects two adjacent vertical lines and may be drawn wherever it is needed.

Find the minimum cost needed to change the ladder so that a traveler starting at top position a arrives at bottom position b.

The first line contains N and M (1 <= N <= 100, 0 <= M <= 500).

The next line contains a, b, X, and Y (0 <= X, Y <= 1,000).

Each of the next M lines contains an integer p describing one horizontal line, in order from top to bottom. This horizontal line connects vertical lines p and p+1.

Print the minimum cost.