Quxiao`s flowers

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

Quxiao 和 xiao bai 是南京理工大学ACM集训队的老队员。他们之间的关系想必是世人都知道的。随着日子一天一天的过去,小白就要出国留学了,留给quxiao的机会也不多了 。quxiao想抓住最后的机会给小白送一束鲜花。由于quxiao和xiaobai一起相处多年,quxiao对小白喜欢的鲜花类型了如指掌。我们用一个整数值v来表示xiaobai对鲜花的喜欢程度(v <= 100)。Quxiao来到花店,花店里有n(0< n < 1001)种鲜花。由于小白不喜欢重复的东西,因此每种鲜花只能选一朵。花店的老板又告诉quxiao,有些花放到一起后,两种花香产生化学反应会使人昏迷,因此有些花是不能一起选的。现在quxiao看着眼花缭乱的花很头疼,为了毕其功于一役,他想买尽可能多的花又要使xiaobai的喜欢程度(总的喜欢程度等于每朵花的喜欢程度之和)最高。但是花太多了,你能编一个程序帮quxiao吗? 注意:不存在这样n种花:c1,c2,c3……cn,ci与ci+1不能放在一起,且cn与c1不能放在一起。

Input

多组输入数据,每组第一行输入两个整数,n和m,分别表示花的种类和不能放在一起的花的对数。 接下来n行中,第i行输入一个数v,表示xiaobai对第i种花的喜欢程度。再接下来m行,每行输入两个数A和B,表示第A种花和第B种花不能放在一起。

Output

每组输出一个整数占一行,为quxiao所能买到的花的xiaobai所喜欢的程度的总和。

Sample Input

3   1
1
1
1
1 2

Sample Output

2

Hint

Source

ZhangFan&boa

提交代码