#P1929. [Balkan2000]Diving

[Balkan2000]Diving

潜水(Diving)

题目描述

每年,奥赫里德都会举办潜水训练班。其中有一项训练:所有学员需要沿着一条水下通道,从岩石的一侧潜到另一侧。

共有 NN 名学员,最初全部在通道的同一侧,最终要求所有学员到达另一侧。大家只有一个氧气瓶。每次潜水必须携带氧气瓶,并且同一时间最多只能有两名学员共用这个氧气瓶。

第 ii 名学员独自通过通道需要 tit_i 个单位时间。如果两名学员结伴潜水,那么他们必须一起行动,耗时为两人独自潜水时间的较大值。

有 MM 对学员彼此不合,每一对这样的学员都不能结伴潜水。不过,他们可以各自单独潜水,也可以与其他允许结伴的学员一起潜水。

氧气瓶只能由潜水的学员携带,在两侧之间移动。为使所有学员最终到达另一侧,允许学员携带氧气瓶多次往返;每次最多两人,瓶中的氧气无限充足。

请计算将全部学员送到另一侧所需的最少总时间。

输入格式

第一行包含两个整数 N,MN,M,分别表示学员人数和不能结伴的学员对数。

接下来 NN 行,每行一个正整数 tit_i,表示第 ii 名学员独自潜水的时间。

接下来 MM 行,每行两个整数 u,vu,v,表示学员 uu 和学员 vv 不能结伴潜水。

输出格式

只输出一行一个整数,表示全部学员到达另一侧所需的最少总时间。

不需要输出具体的移动方案。

输入输出样例

输入样例

4 2
1
2
1
2
3 4
2 3

输出样例

6

样例解释

例如,可以依次进行以下移动(学员编号从 11 开始):

  1. 学员 1,31,3 一起前往另一侧,用时 11;
  2. 学员 11 返回,用时 11;
  3. 学员 2,42,4 一起前往另一侧,用时 22;
  4. 学员 33 返回,用时 11;
  5. 学员 1,31,3 一起前往另一侧,用时 11。

总时间为 1+1+2+1+1=61+1+2+1+1=6,且没有违反不能结伴的限制。

数据范围与约定

  • 1≤N≤60001\le N\le 6000;
  • 0≤M≤60000\le M\le 6000;
  • 本站全部评测数据满足 1≤ti≤1001\le t_i\le100;
  • 1≤u,v≤N1\le u,v\le N,且 u≠vu\ne v;
  • 保证存在至少一种合法方案。

题目来源