Segment Partitioning Under Constraints

You are given a sequence of n numbers \(a_1, a_2, \dots, a_n\). Your task is to partition the sequence into one or more contiguous segments. However, there are two complications:

1. You are given m pairs of numbers (by their positions) that are not allowed to be in the same segment.
2. The cost of forming a segment is given by \(K + S \times (P-Q)\), where \(K\) and \(S\) are provided constants, \(P\) is the maximum value in the segment, and \(Q\) is the minimum value in the segment.

Your goal is to find a valid segmentation (one that does not put any forbidden pair in the same segment) that minimizes the total cost (the sum of the costs for each segment).

Note: All formulas are written in \(\LaTeX\) format.

inputFormat

The first line contains four integers: n (1 ≤ n ≤ 10^3), m (0 ≤ m ≤ 10^4), K and S (\(0 \leq K, S \leq 10^9\)).

The second line contains n integers representing \(a_1, a_2, \dots, a_n\).

Each of the next m lines contains two integers \(u\) and \(v\) (1-indexed, \(u < v\)) indicating that the numbers at positions \(u\) and \(v\) cannot be placed in the same segment.

outputFormat

Output a single integer --- the minimum total cost to partition the sequence satisfying the constraints.

sample

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

30