A22575.分段

省选/NOI-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

给定你n个数a1a2a3...ana_1、a_2、a_3、...、a_n,要求将它们分成若干连续的段。

要求:

  1. 有m对给定的数不能被分到同一段。

  2. 分出一个段的代价是K+S×(PQ)K + S \times (P - Q),其中K和S均为给定的常数,而P则是该段中所有数的最大值,Q是该段中所有数的最小值。

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

输入格式

第一行两个正整数n和m,表示数的个数和不能共存的m对数。

第二行两个非负整数K和S,含义见题面。

第三行n个非负整数,即给定的n个数。

接下来m行每行2个数pip_iqiq_i,表示pip_iqiq_i这两个编号的数不能共存。(编号从1开始)

输出格式

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

输入输出样例

  • 输入#1

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

    输出#1

    11

说明/提示

对于10%的数据,n10n \leq 10

对于30%的数据,n1500n \leq 1500

对于另外10%的数据,S=0S = 0

对于另外30%的数据,m=0m = 0

对于100%的数据,1≤m,n≤100000,0≤K,S,a_i≤100000,1≤pi,qi≤n,pi≠qi。

首页