#1929. [Balkan2000]Diving

题目描述

潜水 每年奥利德湖都有潜水课程。课程中有各项不同的测试。其中一项是通过一条水下通道，从岩石的一端游到另一端。全组N个学生只有一个氧气瓶，两个以上的人不能同时使用一个氧气瓶。每个潜水者有他自己的潜水速度，所以当两个学生一起潜水时，他们的速度与两人 中慢的那个（潜水所用时间较长的那个）的速度相同。有M 对学生不喜欢对方，所以不能在一起潜水。 任务 制作一张计划表，使全组学生从岩石的一端潜到另一端所用的总时间最少。

输入格式

N 是个正整数，表示全组学生的总数。每个学生按照1,2,…,N编了号。N< = 6000 M是个正整数，表示不能一起潜水的学生对数。 M< = 6000 ti 是个正整数，表示第i 个学生岩石一端潜到另一端所须的时间。 氧气瓶只能靠潜水的方式从岩石的一端运到另一端。氧气瓶的容量视为无限。问题至少总有一个解决方案。 第一行是两个整数N 和 M，后N 行每行是一个整数ti 。再后M 行每行是两个整数，表示不能在一起潜水的一对学生的编号。

输出格式

第一行是个整数，代表所有学生潜到对岸所须的最少时间。以后的各行表示对应该最少时间的一个可行计划表。每行表示计划表上的一次潜水。每一行上的一个或两个整数表示表示带着氧气瓶从岩石一端潜到另一端的学生的编号。

样例

样例输入

4 2  

1  

2  

1  

2  

3 4  

2 3  

样例输出

6

数据范围与提示