Problem description


Pielęgnacja Trawnika
(F)
Limit pamięci: 128 MB
Limit czasu: 3.00 s

Na rozległym polu znajduje się N skupisk chwastów. Skupisko o indeksie i leży w punkcie o współrzędnych (Ri,Ci) i początkowo zawiera Ai chwastów. Wszystkie pary współrzędnych (Ri,Ci) są różne, jednak kilka skupisk może znajdować się w tym samym wierszu lub w tej samej kolumnie.

Bajtek musi przeprowadzić dokładnie jedną operację pielęgnacji. Wybiera w tym celu jedno skupisko o indeksie k. Przyjmijmy, że R = Rk, C = Ck oraz X = Ak, gdzie X oznacza liczbę chwastów w wybranym skupisku przed wykonaniem operacji.

Następnie Bajtek próbuje usunąć po X chwastów z każdego skupiska znajdującego się w wierszu R lub w kolumnie C. Liczba chwastów nie może jednak spaść poniżej zera. Jeżeli w skupisku jest mniej niż X chwastów, Bajtek usuwa je wszystkie. Dokładniej, końcowa liczba chwastów w skupisku o indeksie i wynosi

$$ B_i = \begin{cases} \max(0, A_i - X) & \text{gdy } R_i = R \text{ lub } C_i = C,\\ A_i & \text{w przeciwnym przypadku.} \end{cases} $$

Jeżeli skupisko znajduje się jednocześnie w wybranym wierszu i wybranej kolumnie, operacja jest wykonywana na nim tylko raz. Dotyczy to wybranego skupiska, którego końcowa wartość jest równa Bk = 0. Każda wartość Bi jest więc nieujemna.

Bajtek chce tak wybrać skupisko, aby największa końcowa liczba chwastów w pojedynczym skupisku była możliwie najmniejsza. Pomóż mu wyznaczyć tę wartość.

Wejście

W pierwszym wierszu znajduje się liczba całkowita T - liczba niezależnych zestawów testowych.

Opis każdego zestawu testowego rozpoczyna się od wiersza zawierającego liczbę całkowitą N - liczbę skupisk chwastów.

W każdym z kolejnych N wierszy znajdują się trzy liczby całkowite Ri, Ci oraz Ai - odpowiednio numer wiersza, numer kolumny i początkowa liczba chwastów w skupisku o indeksie i.

W obrębie jednego zestawu testowego wszystkie pary (Ri,Ci) są różne.

Wyjście

Dla każdego zestawu testowego wypisz w osobnym wierszu jedną liczbę całkowitą - najmniejszą możliwą wartość max1 ≤ i ≤ NBi po wykonaniu dokładnie jednej operacji pielęgnacji.

Ograniczenia

1 ≤ T ≤ 104, 1 ≤ N ≤ 106, 1 ≤ Ri, Ci, Ai ≤ 109, suma wartości N we wszystkich zestawach testowych nie przekracza 106

Podzadania

Podzadanie Dodatkowe warunki Punkty
1 Ri, Ci ≤ 50 10
2 Ri, Ci ≤ 1000 40
3 Bez dodatkowych ograniczeń 50

Przykład

Wejście Wyjście Wyjaśnienie
3
3
1 1 5
1 2 8
2 1 7
3
1 1 4
2 2 6
3 3 5
4
1 10 9
1 20 6
2 10 7
2 20 4
3
5
4

W pierwszym zestawie wybieramy skupisko (1,1) o wartości 5. Po operacji wartości wynoszą 0, 3 i 2, więc największa z nich to 3.

W drugim zestawie żadne dwa skupiska nie leżą w tym samym wierszu ani w tej samej kolumnie. Po wybraniu skupiska o wartości 6 tylko ono zmienia wartość na 0, a największą z pozostałych wartości jest 5.

W trzecim zestawie wybieramy skupisko (1,10) o wartości 9. Z pierwszego, drugiego i trzeciego skupiska usuwamy odpowiednio 9, 6 i 7 chwastów, ponieważ liczba chwastów nie może być ujemna. Końcowe wartości to 0, 0, 0 i 4, zatem odpowiedź wynosi 4.

Wejście Wyjście Wyjaśnienie
3
1
1 1 100
4
5 1 3
5 2 10
5 3 6
5 4 1
4
1000000000 1000000000 4
999999999 999999998 10
999999997 999999996 7
999999995 999999994 2
0
0
7

W pierwszym zestawie istnieje tylko jedno skupisko. Po jego wybraniu pozostaje w nim 0 chwastów.

W drugim zestawie wszystkie skupiska znajdują się w wierszu 5. Wybieramy skupisko o wartości 10 i usuwamy wszystkie chwasty z każdego skupiska. Końcowe wartości to 0, 0, 0 i 0, więc ich maksimum jest równe 0.

W trzecim zestawie każde skupisko leży w innym wierszu i innej kolumnie. Wybieramy skupisko o wartości 10; zmienia się ono na 0, a największa spośród pozostałych wartości wynosi 7.