33831번 - Heavy Metal 다국어

문제

Bajtazar, wokalista kapeli heavy-metalowej Algosia in Antichains, przygotowuje się do koncertu w Bajtoszycach. Oprócz przygotowania ulubionych piosenek fanów zgromadzonych na widowni, równie ważne jest przygotowanie sprzętu nagłaśniającego.

Zestaw nagłaśniający składa się z $n$ ruterów oraz $m$ wzmacniaczy. Mikrofon jest podłączony do rutera numer 1ドル,ドル a głośnik do rutera $n$. Każdy ze wzmacniaczy łączy dwa rutery (wejściowy i wyjściowy) oraz ma współczynnik wzmocnienia $w_i$. Każdy ruter ma także maksymalną przepustowość $p_i$.

Sygnał z mikrofonu ma moc 1ドル$. Bajtazar może tak skonfigurować zestaw, aby przesłać sygnał z mikrofonu przez dowolny ciąg ruterów połączonych wzmacniaczami. Moc sygnału po przejściu przez wzmacniacz przemnaża się przez współczynnik wzmocnienia danego wzmacniacza. Jeśli w dowolnym momencie moc aktualnie przesyłanego sygnału przekroczy przepustowość rutera, przez który przechodzi, dojdzie do przepalenia tego rutera, czego Bajtazar absolutnie chce uniknąć.

Sygnał może przejść przez ten sam ruter lub wzmacniacz dowolną liczbę razy. Bajtazar chce przesłać sygnał docelowo do głośnika, osiągając maksymalne możliwe wzmocnienie, ale nie przekraczając przepustowości żadnego z ruterów. Pomóż mu to osiągnąć.

입력

W pierwszym wierszu znajduje się jedna liczba całkowita $T$ (1ドル ≤ T ≤ 100$) oznaczająca liczbę zestawów nagłaśniających posiadanych przez Bajtazara. Dalej znajduje się $T$ opisów kolejnych zestawów nagłaśniających.

W pierwszym wierszu opisu znajdują się dwie liczby całkowite $n$ i $m$ (1ドル ≤ n, m$) oznaczające liczbę ruterów oraz liczbę wzmacniaczy.

W kolejnym wierszu znajduje się ciąg $n$ liczb całkowitych $p_1, p_2, \dots , p_n$ (1ドル ≤ p_i ≤ 10^9$), oznaczających przepustowości kolejnych ruterów.

W kolejnych $m$ wierszach znajdują się opisy wzmacniaczy, gdzie $i$-ty z nich składa się z trzech liczb całkowitych $a_i,ドル $b_i$ oraz $w_i$ (1ドル ≤ a_i , b_i ≤ n,ドル 1ドル ≤ w_i ≤ 10^9$) oznaczających odpowiednio ruter wejściowy, ruter wyjściowy oraz współczynnik wzmocnienia $i$-tego wzmacniacza.

Suma $n$ we wszystkich zestawach nie przekracza 100ドル,ドル a suma m nie przekracza 200ドル$.

출력

Na wyjście należy wypisać $T$ wierszy; w $i$-tym z nich powinna znaleźć się jedna liczba całkowita oznaczająca maksymalne możliwe wzmocnienie sygnału w $i$-tym zestawie nagłaśniającym. Jeśli nie jest możliwe przesłanie sygnału do głośnika przy pomocy $i$-tego zestawu, należy zamiast tego wypisać $-1$.

제한

노트

Wyjaśnienie do przykładu: W pierwszym zestawie nagłaśniającym optymalne skonfigurowanie przesyła sygnał w następujący sposób:

1ドル$ → 1ドル$ (sygnał o mocy 2ドル$) → 2ドル$ (sygnał o mocy 2ドル \cdot 3 = 6$) → 1ドル$ (sygnał o mocy 6ドル \cdot 37 = 222$) → 2ドル$ (sygnał o mocy 222ドル \cdot 3 = 666$)

W drugim zestawie optymalne rozwiązanie to:

1ドル$ → 1ドル$ (sygnał o mocy 2ドル$) → 1ドル$ (sygnał o mocy 2ドル \cdot 2 = 4$) → 1ドル$ (sygnał o mocy 4ドル \cdot 2 = 8$) → 2ドル$ (sygnał o mocy 8ドル \cdot 1 = 8$) → 2ドル$ (sygnał o mocy 8ドル \cdot 3 = 24$) → 2ドル$ (sygnał o mocy 24ドル \cdot 3 = 72$) → 2ドル$ (sygnał o mocy 72ドル \cdot 3 = 216$) → 3ドル$ (sygnał o mocy 216ドル \cdot 1 = 216$) → 3ドル$ (sygnał o mocy 216ドル \cdot 5 = 1080$)

W trzecim zestawie:

1ドル$ → 1ドル$ (sygnał o mocy 2ドル$) → 1ドル$ (sygnał o mocy 2ドル \cdot 2 = 4$) → 2ドル$ (sygnał o mocy 4ドル \cdot 1 = 4$)

W czwartym zestawie przesłanie sygnału wzmacniaczem skutkowałoby sygnałem o mocy 1ドル,円 000,円 000,円 000$ przekraczającej przepustowość rutera numer 2ドル$. Stąd przekazanie sygnału o jakiejkolwiek mocy nie jest możliwe.