Godzilla

Memory limit: 32 MB

The evil monster Godzilla has decided to visit Byteburg again. Each day the monster crawls out of the ocean, reaches one of the city's sky-scrapers and eats it together with everyone who lives inside the building. It takes Godzilla a whole day to eat the sky-scraper; afterwards it goes back into the blue. When walking through the city, the monster accidentally destroys with its tail all the sky-scrapers it passes on its way.

Obviously, the citizens of Byteburg find this situation difficult to bear. That is why each night from each sky-scraper one citizen escapes to the countryside.

The sky-scrapers in Byteburg are located at junctions. A every junction there is exactly one sky-scraper. The junctions are connected with bidirectional streets. One of the junctions is located just next to the ocean - it is where Godzilla starts its deadly journey each day. On every journey the monster moves only along streets.

Godzilla noticed that it must hurry up with its feast and choose both the sky-scrapers to eat and the streets on its way really carefully. Of course it cannot choose to eat a sky-scraper that has already been eaten or destroyed on the way. What is the maximum number of people that Godzilla can eat before the city gets totally uninhabited?

Input

The first line of input contains two integers and (, ) that represent the number of junctions and the number of streets respectively. The junctions are numbered 1 through , the junction number 1 is the one located next to the ocean. The next line contains a sequence of integers () that describe the number of people who live in the sky-scrapers next to the respective junctions. Each of the following lines contains two integers and (, ) which mean that there is a street connecting the junctions no. and no. . Each junction is reachable from the junction number 1.

Output

Your program should print the number of people eaten by Godzilla provided that it chooses its eating and moving plan optimally.

Example

For the input data:

5 5
1 3 2 4 7
1 2
1 3
2 3
2 4
3 5

the correct result is:

11

Task author: Tomasz Idziaszek.