读书

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file reading.in Output file reading.out

【题目描述】


放暑假了,LRJ想趁假期提高一下自己的计算机水平,于是他从学校图书馆借了N本计算机科学方面的书,这N本书的编号依次为0~N-1。

读完第i本书,LRJ需要花费time[i]分钟,但是有一些书的内容是相近的,如果第i本书与第j本书内容相近,那么如果LRJ读完了第i本书,再读第j本书的时候只需要floor(time[j]/2)分钟的时间即可(其中floor()表示对括号中的式子进行下取整);当然,如果LRJ先读完了第j本书,那么再读第i本书的时候只需floor(time[i]/2)的时间。现在你的任务是告诉LRJ,他最少可以用多少分钟读完这N本书。



【输入格式】


第一行有两个整数N(0<=N<=100)和M(0<=M<=N(N-1)/2)。N为书的总数,有M对书内容相近。

接下来有N行,分别表示time[0],time[1],...及time[N-1],(1<=time[i]<=10^5)。

再接下来有M行,每行有两个整数(i,j),表示第i本书与第j本书内容相近。

输出文件以N=0,M=0表示结束。



【输出格式】

对于每组测试数据,输出仅一行,即最少时间。

【样例输入】

2 1
6
10
0 1
3 2
1
2
3
0 1
1 2
3 1
2
4
6
0 1
0 0 

【样例输出】

11
3
10

【提示】

对于第一组数据,如果LRJ读的顺序为(0,1),则总的时间为6+10/2=11,如果读的顺序为(1,0),则总的读书时间为10+6/2=13.

【来源】

在此键入。