P2248 分段

给你 $n$ 个数 $a_1 \sim a_n$，要求将它们分成若干连续的段，其中有 $m$ 对给定的数不能被分到同一段。 分出一个段的代价是： $$K + S \times (P - Q)$$ 其中 $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}$ 不能共存。

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

对于 $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$。