Лёша решил отправиться в туристическую поездку по стране.
Для простоты стоит считать, что в стране есть \(n\) городов и \(m\) двусторонних дороги, которые их соединяют. Лёша живёт в городе \(s\) и изначально находится в нём. Каждый город в стране по своему хорош, и чтобы сравнивать города между собой, Лёша поставил каждому городу оценку \(w_i\), которая тем больше, чем интереснее город кажется Лёше.
Лёша считает, что его поездка по стране будет интересной только в том случае, если ему ни в какой момент времени не придётся ехать назад по дороге, по которой он только что проехал. Другими словами, если Лёша переехал из города \(u\) в город \(v\), следующим в своей поездке Лёша может выбрать любой город, соединённый с \(v\) дорогой, кроме города \(u\).
Помогите Лёше спланировать поездку так, чтобы сумма оценок по всем посещённым им городам была максимальна. Считайте, что оценка любого посещённого города учитывается в сумме только один раз, даже если город был посещён не единожды.
Выходные данные
Выведите одно целое число — максимальную сумму оценок посещённых городов, которую можно получить.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 7
2 2 8 6 9
1 2
1 3
2 4
3 2
4 5
2 5
1 5
2
|
27
|
|
2
|
10 12
1 7 1 9 3 3 6 30 1 10
1 2
1 3
3 5
5 7
2 3
5 4
6 9
4 6
3 7
6 8
9 4
9 10
6
|
61
|