#P1929. [Balkan2000]Diving
[Balkan2000]Diving
潜水(Diving)
题目描述
每年,奥赫里德都会举办潜水训练班。其中有一项训练:所有学员需要沿着一条水下通道,从岩石的一侧潜到另一侧。
共有 名学员,最初全部在通道的同一侧,最终要求所有学员到达另一侧。大家只有一个氧气瓶。每次潜水必须携带氧气瓶,并且同一时间最多只能有两名学员共用这个氧气瓶。
第 名学员独自通过通道需要 个单位时间。如果两名学员结伴潜水,那么他们必须一起行动,耗时为两人独自潜水时间的较大值。
有 对学员彼此不合,每一对这样的学员都不能结伴潜水。不过,他们可以各自单独潜水,也可以与其他允许结伴的学员一起潜水。
氧气瓶只能由潜水的学员携带,在两侧之间移动。为使所有学员最终到达另一侧,允许学员携带氧气瓶多次往返;每次最多两人,瓶中的氧气无限充足。
请计算将全部学员送到另一侧所需的最少总时间。
输入格式
第一行包含两个整数 ,分别表示学员人数和不能结伴的学员对数。
接下来 行,每行一个正整数 ,表示第 名学员独自潜水的时间。
接下来 行,每行两个整数 ,表示学员 和学员 不能结伴潜水。
输出格式
只输出一行一个整数,表示全部学员到达另一侧所需的最少总时间。
不需要输出具体的移动方案。
输入输出样例
输入样例
4 2
1
2
1
2
3 4
2 3
输出样例
6
样例解释
例如,可以依次进行以下移动(学员编号从 开始):
- 学员 一起前往另一侧,用时 ;
- 学员 返回,用时 ;
- 学员 一起前往另一侧,用时 ;
- 学员 返回,用时 ;
- 学员 一起前往另一侧,用时 。
总时间为 ,且没有违反不能结伴的限制。
数据范围与约定
- ;
- ;
- 本站全部评测数据满足 ;
- ,且 ;
- 保证存在至少一种合法方案。