题目描述
由于换季,商场推出优惠活动,以超低价格出售若干种商品。但是商场为避免过分亏本,规定某些商品不能同时购买,而且每种超低价商品只能买一件。身为顾客的你想获得最大的实惠,也就是争取节省最多的钱。经过仔细研究,我们发现商场出售的超低价商品中,不存在以下这种情况:n(n>=3)种商品C1,C2,C3,……,Cn,其中Ci和Ci+1是不能同时购买的(i=1,2,……,n-1),而且C1和Cn也不能同时购买。
请编程计算可以接生的最大金额数。
输入格式
第一行两个整数K,M(1<=K<=1000),其中K表示超低价商品数,K种商品的编号依次为1,2,3,……,K;M表示不能同时购买的商品对数。
接下来K行,第i行有一个整数Xi表示购买编号为i的商品可以节省的金额(1<=Xi<=100)。
再接下来M行,每行两个数A,B,表示A和B不能同时购买,1<=A,B<=K,A≠B。
输出格式
仅一行一个整数,表示能节省的最大金额数。
样例输入
样例输出