Вам надано простий неорієнтований граф із \(N\) вершинами та \(M\) ребрами. \(i\)-е ребро з'єднує вершини \(U_i\) і \(V_i\). Вершина \(i\) має натуральне число \(A_i\) написане на ній.

Ви повторите наступну операцію \(N\) разів.

• Виберіть вершину \(x\), яку ще не видалено, і видаліть вершину \(x\) і всі ребра, пов’язані з вершиною \(x\). Вартість цієї операції є сумою цілих чисел, записаних на вершинах, безпосередньо з’єднаних ребром з вершиною \(x\), які ще не видалені.

Ми визначаємо вартість усіх операцій \(N\) як максимум витрат на окремі операції. Знайдіть мінімально можливу вартість усіх операцій.

Обмеження

• \(1 \le N \le 2 \times 10^5\)
• \(0 \le M \le 2 \times 10^5\)
• \(1 \le A_i \le 10^9\)
• \(1 \le U_i,V_i \le N\)
• Наведений граф простий.
• Усі значення у вхідних даних є цілими числами.

Формат вхідних даних

Перший рядок містить цілі числа \(N,M\)

Наступний  рядок містить \(N\) цілих чисел \(A_i\)

Наступні  \(M\) рядків містять цілі числа \(U_i, V_i\)

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть відповідь.

Примітка

До прикладу 1:

Виконуючи наступні операції, максимальна вартість \(N\) операцій може становити 3.

• Виберіть вершину 3. Вартість \(A_1=3\).
• Виберіть вершину 1. Вартість \(A_2+A_4=3\).
• Виберіть вершину 2. Вартість 0.
• Виберіть вершину 4. Вартість 0.

Максимальна вартість \(N\) операцій не може бути 2 або менше, тому рішення дорівнює 3.

Приклад вхідних даних

4 3
3 1 4 2
1 2
1 3
4 1

Приклад вихідних даних

3

Приклад вхідних даних

7 13
464 661 847 514 74 200 188
5 1
7 1
5 7
4 1
4 5
2 4
5 2
1 3
1 6
3 5
1 2
4 6
2 7

Приклад вихідних даних

1199