C. Ребенок и игрушка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В день детей ребенок получил в подарок от Delayyy игрушку. Но ребенок такой вредный, что он ждет — не дождется шанса сломать ее.

Игрушка состоит из n деталей, соединенных m веревочками. Каждая веревочка соединяет две детали, при этом каждая пара деталей соединена не более чем одной веревочкой. Чтобы разломать игрушку, ребенок должен оторвать все ее детали. Ребенок может отрывать по одной детали за раз, на каждое отрывание он тратит энергию. Обозначим значение энергии детали i как vi. Ребенок тратит vf1 + vf2 + ... + vfk энергии на отрывание детали i, где f1, f2, ..., fk — еще не оторванные детали, напрямую соединенные веревочками с i-й.

Помогите ребенку посчитать минимальную суммарную энергию, которую он должен потратить на отрывание всех n деталей.

Входные данные

В первой строке записано два целых числа, n и m (1 ≤ n ≤ 1000; 0 ≤ m ≤ 2000). Во второй строке записано n целых чисел: v1, v2, ..., vn (0 ≤ vi ≤ 105). Затем следует m строк, в каждой записано по два целых числа, xi и yi, обозначающих веревочку, соединяющую детали xi и yi (1 ≤ xi, yi ≤ n; xi ≠ yi).

Считайте, что все детали пронумерованы от 1 до n.

Выходные данные

Выведите минимальную суммарную энергию, необходимую для отрывания всех n деталей игрушки.

Примеры
Входные данные
4 3
10 20 30 40
1 4
1 2
2 3
Выходные данные
40
Входные данные
4 4
100 100 100 100
1 2
2 3
2 4
3 4
Выходные данные
400
Входные данные
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
Примечание

Одна из оптимальных последовательностей действий в первом примере такова:

  • Сначала оторвите деталь 3, затрата энергии равна 20.
  • Затем оторвите деталь 2, затрата энергии равна 10.
  • Потом оторвите деталь 4, затрата энергии равна 10.
  • Наконец, оторвите деталь 1, затрата энергии равна 0.

Таким образом, всего ребенок затрачивает 20 + 10 + 10 + 0 = 40 единиц энергии, это минимально возможный ответ.

Во втором примере ребенок потратит 400 единиц энергии вне зависимости от порядка отрывания деталей.