题目描述

过年了，各大商场都有促销活动，什么满多少减多少，打折，抽奖等等。比如和谐百货就推出优惠活动，以超低价格出售商品。但是，商场为了避免过分亏本，规定某些商品不能同时购买，而且每种超低价商品只能买一件。

作为未来的伟大程序猿的你，决定写一个程序来做出最佳判断以节省最多的钱。经过研究，你发现，商场出售的超低价商品中不存在以下这种情况：$n$ 种商品，$C_1,C_2......,C_n$，其中$C_i$ 和 $C_{i+1}$是不能一起购买的（$i=1，2，3.....，n-1$），而且 $C_1$ 和 $C_n$ 也不能同时购买。

输入格式

输入共 $K+M+1$ 行。

第一行输入两个整数 $K$，$M$，其中 $K$ 表示超低价商品数，$K$ 种商品的编号依次为$1，2，3...，K$，$M$ 表示不能同时购买的商品对数。

接下来的 $K$ 行，第 $i$ 行有一个整数 $X_i$ 表示购买编号为 $i$ 的商品可以节省的金额。

接下来的 $M$ 行，每行两个数 $A$ 和 $B$，表示 $A$ 和 $B$ 不能同时购买。

输出格式

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

样例输入输出

样例输入

3 1
1
1
1
1 2

样例输出

2

数据范围

对于 $100%$ 的数据，保证 $1 \le K \le 1000,1 \le X \le 100$。