题号：NC273398
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
Alice is a lead singer in a band. Her band is on a tour, holding concerts every month. However, they don't want to stay in the same city for two consecutive months. Therefore, at the end of each month, the band will move to a city adjacent to the current one. There are a total of 
cities, connected by 
roads, and holding a concert in the 
-th city for a month can generate revenue of 
.
Alice's home is in the first city, so the band will hold the first concert there. The concert tour lasts for
months in total, and Alice wants to return to the first city for the final concert in the -th month. In other words, in the -th month, Alice must be in the first city.
Now, Alice wants to know how much revenue she can maximize during the months.
Alice's home is in the first city, so the band will hold the first concert there. The concert tour lasts for
Now, Alice wants to know how much revenue she can maximize during the
输入描述:
The first line contains three integers(
), as described in the problem statement.
The second line containsintegers
(
), representing the revenue Alice can earn by holding a concert in the
-th city for a month.
The nextlines each contain two integers
(
), indicating there is a bidirectional road between cities
and
.
输出描述:
Output an integer representing the maximum revenue that can be earned. If Alice cannot stay in the first city for the-th month, output -1.