B"If you say that Arkady is a bit old-fashioned playing checkers, you won't be right. There is also a modern computer game Arkady and his friends are keen on. We won't discuss its rules, the only feature important to this problem is that each player has to pick a distinct hero in the beginning of the game. There are 2 teams each having n players and 2n heroes to distribute between the teams. The teams take turns picking heroes: at first, the first team chooses a hero in its team, after that the second team chooses a hero and so on. Note that after a hero is chosen it becomes unavailable to both teams. The friends estimate the power of the i -th of the heroes as p_i . Each team wants to maximize the total power of its heroes. However, there is one exception: there are m pairs of heroes that are especially strong against each other, so when any team chooses a hero from such a pair, the other team must choose the other one on its turn. Each hero is in at most one such pair. This is an interactive problem. You are to write a program that will optimally choose the heroes for one team, while the jury's program will play for the other team. Note that the jury's program may behave inefficiently, in this case you have to take the opportunity and still maximize the total power of your team. Formally, if you ever have chance to reach the total power of q or greater regardless of jury's program choices, you must get q or greater to pass a test. The first line contains two integers n and m ( 1 <= n <= 10^3 , 0 <= m <= n ) -- the number of players in one team and the number of special pairs of heroes. The second line contains 2n integers p_1, p_2, ldots, p_{2n} ( 1 <= p_i <= 10^3 ) -- the powers of the heroes. Each of the next m lines contains two integer a and b ( 1 <= a, b <= 2n , a ne b ) -- a pair of heroes that are especially strong against ea"...