题目背景

Burza przetoczyła się przez miasto Mitakihara.

Miejskie biuro meteorologiczne nie zdążyło jeszcze zainstalować żadnych urządzeń monitorujących, więc aby określić stan burzy, trzeba polegać na danych z anemometrów rozmieszczonych w mieście. To zadanie powierzono Tobie – nowo zatrudnionemu inżynierowi danych w biurze meteorologicznym.

Treść zadania

W mieście znajduje się $M$ głównych ulic, które łączą $N$ skrzyżowań. Na każdym skrzyżowaniu znajduje się anemometr, a odczyt na skrzyżowaniu $i$ wynosi $v_i$. Im wyższy odczyt, tym silniejszy wiatr.

Na ulicach może wystąpić „efekt zwężenia” (efekt Venturiego), czyli zjawisko, w którym przepływ powietrza przez wąski obszar powoduje spadek ciśnienia i wzrost prędkości przepływu. Prowadzi to do zwiększenia prędkości wiatru na danej ulicy, co sprawia, że odczyty anemometrów na skrzyżowaniach połączonych tą ulicą są wyższe niż wartości rzeczywiste. Intensywność tego efektu dla ulicy $i$ wynosi $e_i$.

Aby określić zasięg centrum burzy, musisz znaleźć zbiór $S$ składający się z co najwyżej $K$ ulic (może to być $0$ ulic; pamiętaj, że nie można wybrać tej samej ulicy wielokrotnie), tak aby zmaksymalizować wartość: $$ \sum\limits_{x\in I(S)} v_x -\sum\limits_{y\in S} e_y \tag{1} $$ gdzie $I(S)$ oznacza zbiór wszystkich skrzyżowań połączonych z co najmniej jedną ulicą należącą do $S$.

Jeśli skrzyżowanie jest połączone z więcej niż jedną ulicą z $S$, jest ono liczone tylko raz. Eksperci meteorologiczni przypuszczają, że na obrzeżach burzy może występować wiele mniejszych cyklonów, co oznacza, że może istnieć wiele niezależnych centrów burzy, dlatego wybrany zbiór ulic nie musi być spójny.

Wykonaj zadanie jak najszybciej; od Twoich wyników zależy, czy biuro meteorologiczne podejmie dalsze kroki.

Wejście

Pierwsza linia zawiera liczbę całkowitą $T$, oznaczającą liczbę zestawów danych. Dla każdego zestawu danych:

• Pierwsza linia zawiera trzy liczby całkowite $N, M, K$, oznaczające odpowiednio liczbę skrzyżowań, liczbę ulic oraz górny limit liczby wybranych ulic. Skrzyżowania są ponumerowane od $1$ do $N$, a ulice od $1$ do $M$.
• Druga linia zawiera $N$ nieujemnych liczb całkowitych, oznaczających $v_1, v_2, \dots, v_N$.
• Następne $M$ linii zawiera po trzy liczby całkowite $a_i, b_i, e_i$, oznaczające, że ulica $i$ łączy skrzyżowania $a_i$ oraz $b_i$, a intensywność efektu zwężenia wynosi $e_i$.

Wyjście

Dla każdego zestawu danych wypisz w jednej linii liczbę całkowitą będącą maksymalną wartością wyrażenia $(1)$.

Przykład

Przykład 1

Wejście:

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

Wyjście:

27

Uwagi do przykładu 1

Zbiór $S$ powinien zawierać ulicę $(2,5)$ oraz ulicę $(3,4)$, których suma $e_i$ wynosi $3$. W tym przypadku $I(S)$ zawiera węzły $2, 3, 4, 5$, których suma $v_i$ wynosi $30$.

Podzadania

Dla wszystkich danych wejściowych:

• $\sum 2^K(N+M)\leq 10^6$, gdzie suma dotyczy wszystkich zestawów danych.
• $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$
• Graf nieskierowany utworzony przez wszystkie skrzyżowania i ulice nie zawiera pętli własnych, ale może zawierać krawędzie wielokrotne, może być niespójny i może zawierać izolowane wierzchołki.
• Gwarantuje się, że wynik nie przekracza $2\cdot 10^9$.

Podzadanie 1: $30$ punktów, $\sum (N+M)\leq 1500$

Podzadanie 2: $30$ punktów, $K\leq 9$

Podzadanie 3: $40$ punktów, brak dodatkowych ograniczeń

Epilog

W przerwie między debugowaniem spojrzałeś przez okno i zamarłeś na widok oślepiającego światła słonecznego.

Nie wiadomo kiedy, burza ucichła.