题目描述

给你 $n$ 个数 $a_1 \sim a_n$，要求将它们分成若干连续的段，其中有 $m$ 对给定的数不能被分到同一段。

分出一个段的代价是：

其中 $K$ 和 $S$ 均为给定的常数，$P$ 是该段中所有数的最大值，$Q$ 是该段中所有数的最小值。

你需要求出每段代价之和最小的分段方案。

输入格式

第一行两个正整数 $n,m$。

第二行两个非负整数 $K,S$。

第三行 $n$ 个非负整数 $a_1 \sim a_n$。

下面 $m$ 行，每行 $2$ 个正整数 $p_i,q_i$，表示 $a_{p_i},a_{q_i}$ 不能共存。

输出格式

输出仅一行，表示最小的每段代价之和。

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

11

提示

对于 $10\%$ 的数据，$n \leq 10$。

对于 $30\%$ 的数据，$n \leq 1500$。

对于另外 $10\%$ 的数据，$S = 0$。

对于另外 $30\%$ 的数据，$m = 0$。

对于 $100\%$ 的数据，$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$。