Description

You are given $n$ numbers $a_1 \sim a_n$, and you need to partition them into several contiguous segments, with the constraint that there are $m$ specified pairs of numbers that cannot be placed in the same segment.

The cost of creating one segment is:

where $K$ and $S$ are given constants, $P$ is the maximum value in that segment, and $Q$ is the minimum value in that segment.

You need to find a partitioning scheme that minimizes the sum of costs over all segments.

Input Format

The first line contains two positive integers $n,m$.

The second line contains two non-negative integers $K,S$.

The third line contains $n$ non-negative integers $a_1 \sim a_n$.

Each of the next $m$ lines contains $2$ positive integers $p_i,q_i$, indicating that $a_{p_i},a_{q_i}$ cannot be in the same segment.

Output Format

Output a single line containing the minimum possible sum of the costs over all segments.

5 2
3 1
2 3 12 14 16
2 3
3 1

11

Hint

For $10\%$ of the testdata, $n \leq 10$.

For $30\%$ of the testdata, $n \leq 1500$.

For another $10\%$ of the testdata, $S = 0$.

For another $30\%$ of the testdata, $m = 0$.

For $100\%$ of the testdata, $1 \le m,n \le 10^5$, $0 \le K,S,a_i \le 10^5$, $1 \le p_i,q_i \le n$, $p_i \ne q_i$.

Translated by ChatGPT 5