Problem description
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 |
|
|
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 |
|
|
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. |