购物问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

由于换季,GDOI商场推出优惠活动,以超低价格出售若干种商品。但是,商场为避免过分亏本,规定某些商品不能同时购买,而且每种超低价商品只能买一件。身为顾客的你想获得最大的实惠,也就是争取节省最多的钱。经过仔细研究,我们发现,商场出售的超低价商品中,不存在以下这种情况:

n(3≤n)种商品C1,C2,...,Cn,其中Ci和Ci+1是不能同时购买的(i=1,2,...,n-1),而且C1和Cn也不能同时购买。

请编程计算可以节省的最大金额数。

Input

第1行两个整数K,M(1≤K≤1000),其中K表示超低价商品数,K种商品的编号依次为1,2,...,K;M表示不能同时购买的商品对数。

接下来的K行,第i行有一个整数Xi表示购买编号为i的商品可以节省的金额(1≤Xi≤100)。

再接下来M行,每行两个数A和B,表示A和B不能同时购买,1≤A≤K,1≤B≤K,A≠B。

Output

仅一个整数,表示能节省的最大金额数。

Sample Input

3 1
1
1
1
1 2

Sample Output

2

Hint

Source