题目背景

Шторм обрушился на город Митакихара.

Метеорологическое бюро города еще не успело установить системы мониторинга, поэтому для определения состояния шторма приходится полагаться на данные анемометров, установленных в городе. Эта задача была поручена вам — новому инженеру данных в метеорологическом бюро.

Условие задачи

В городе есть $M$ главных улиц, соединяющих $N$ перекрестков. На каждом перекрестке установлен анемометр, показания которого в перекрестке $i$ равны $v_i$. Чем выше значение, тем сильнее ветер.

На улицах может возникать «эффект Вентури» — явление, при котором давление падает, а скорость потока возрастает при прохождении через узкие участки. Это приводит к увеличению скорости ветра на улице, из-за чего показания анемометров на перекрестках, соединенных этой улицей, оказываются завышенными по сравнению с реальными значениями. Интенсивность этого эффекта для $i$-й улицы равна $e_i$.

Чтобы определить границы эпицентра шторма, вам нужно найти множество $S$, состоящее не более чем из $K$ улиц (можно выбрать $0$ улиц; обратите внимание, что нельзя выбирать одну и ту же улицу дважды), которое максимизирует следующее выражение: $$ \sum\limits_{x\in I(S)} v_x -\sum\limits_{y\in S} e_y \tag{1} $$ где $I(S)$ обозначает множество всех перекрестков, соединенных хотя бы с одной улицей из $S$.

Если перекресток соединен более чем с одной улицей из $S$, он учитывается только один раз. Метеорологи предполагают, что на периферии шторма могут существовать несколько небольших циклонов, что может привести к наличию нескольких независимых центров шторма, поэтому выбранное вами множество улиц не обязательно должно быть связным.

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

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

Первая строка содержит целое положительное число $T$, количество тестовых случаев. Далее для каждого тестового случая:

• Первая строка содержит три целых положительных числа $N, M, K$, обозначающих количество перекрестков, количество улиц и верхний предел количества выбираемых улиц соответственно. Перекрестки пронумерованы от $1$ до $N$, улицы — от $1$ до $M$.
• Вторая строка содержит $N$ неотрицательных целых чисел, представляющих $v_1, v_2, \dots, v_N$.
• Следующие $M$ строк содержат по три целых числа $a_i, b_i, e_i$, означающих, что улица $i$ соединяет перекрестки $a_i$ и $b_i$, а интенсивность эффекта Вентури на ней равна $e_i$.

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

Для каждого тестового случая выведите одно целое число — максимальное значение выражения $(1)$.

Примеры

Пример 1

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

1
5 5 2
1 2 4 8 16
1 2 1
1 3 2
3 4 2
4 5 2
2 5 1

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

27

Примечание к примеру 1

Множество $S$ должно содержать улицы $(2,5)$ и $(3,4)$, сумма их значений $e_i$ равна $3$. В этом случае $I(S)$ включает узлы $2, 3, 4, 5$, сумма их значений $v_i$ равна $30$.

Подзадачи

Для всех данных:

• $\sum 2^K(N+M)\leq 10^6$, где знак суммы означает суммирование по всем тестовым случаям в одном наборе данных.
• $1\leq T\leq 5$
• $1\leq N, M, K$
• $0\leq e_i, v_i\leq 10^8$
• $1\leq a_i, b_i\leq N$
• Неориентированный граф, образованный всеми перекрестками и улицами, не содержит петель, но может содержать кратные ребра, может быть несвязным и содержать изолированные вершины.
• Гарантируется, что ответ не превышает $2\cdot 10^9$.

Подзадача 1: $30$ баллов, $\sum (N+M)\leq 1500$

Подзадача 2: $30$ баллов, $K\leq 9$

Подзадача 3: $40$ баллов, без дополнительных ограничений

Послесловие

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

Неизвестно когда, но шторм уже стих.