В день детей ребенок получил в подарок от Delayyy игрушку. Но ребенок такой вредный, что он ждет — не дождется шанса сломать ее.
Игрушка состоит из n деталей, соединенных m веревочками. Каждая веревочка соединяет две детали, при этом каждая пара деталей соединена не более чем одной веревочкой. Чтобы разломать игрушку, ребенок должен оторвать все ее детали. Ребенок может отрывать по одной детали за раз, на каждое отрывание он тратит энергию. Обозначим значение энергии детали i как vi. Ребенок тратит vf1 + vf2 + ... + vfk энергии на отрывание детали i, где f1, f2, ..., fk — еще не оторванные детали, напрямую соединенные веревочками с i-й.
Помогите ребенку посчитать минимальную суммарную энергию, которую он должен потратить на отрывание всех n деталей.
Выходные данные
Выведите минимальную суммарную энергию, необходимую для отрывания всех n деталей игрушки.
Примечание
Одна из оптимальных последовательностей действий в первом примере такова:
- Сначала оторвите деталь 3, затрата энергии равна 20.
- Затем оторвите деталь 2, затрата энергии равна 10.
- Потом оторвите деталь 4, затрата энергии равна 10.
- Наконец, оторвите деталь 1, затрата энергии равна 0.
Таким образом, всего ребенок затрачивает 20 + 10 + 10 + 0 = 40 единиц энергии, это минимально возможный ответ.
Во втором примере ребенок потратит 400 единиц энергии вне зависимости от порядка отрывания деталей.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
10 20 30 40
1 4
1 2
2 3
|
40
|
|
2
|
4 4
100 100 100 100
1 2
2 3
2 4
3 4
|
400
|
|
3
|
7 10
40 10 20 10 20 80 40
1 5
4 7
4 5
5 2
5 7
6 4
1 6
1 3
4 3
1 4
|
160
|