#1613. 购物(shop)

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

商场推出优惠活动,以超低价出售若干种商品。但是,商场为避免过分亏本,规定某些商品不能同时购买,而且每种超低价商品只能买一件。

身为顾客的你想获得最大的实惠,也就是争取节省最多的钱。经过仔细研究,发现商场出售的超低价商品中,不存在以下情况:   n(n>=3)种商品C1,C2,…..,Cn,其中Ci,Ci+1是不能同时购买的(i=1,2…,n-1)并且C1, Cn也不能同时购买。   编程计算可以节省的最大金额数。

输入格式

第一行两个整数K,M.其中K表示超低价商品数。K种商品的编号依次为1,2,…,K。M表示不能同时购买的商品对数.接下来K行,第i行有一个整数Xi表示购买编号为i的商品可以节省的金额.再接下来M行,每行两个数A ,B,表示A和B不能同时购买,1<=A<=K,1<=B<=K,A<>B

输出格式

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

样例

样例输入1

3 1 
1
1
1 
1 2

样例输出1

2

数据范围与提示

30%1<=K,M<=10

60%1<=K,M<=100

100%1<=K,M<=1000

1<=Xi<=100