26682번 - Samochody dostawcze 다국어

문제

Bajtazar jest logistykiem w firmie dostarczającej zapasy do sklepów. W mieście, w którym operuje jego firma, sieć drogowa składa się z poziomych ulic (biegnących z zachodu na wschód) oraz pionowych alei (biegnących z południa na północ). Każda sąsiednia para ulic oraz alei oddalona jest od siebie o jeden kilometr. Ulice numerujemy liczbami całkowitymi w kolejności z południa na północ, a aleje numerujemy w kolejności z zachodu na wschód. Skrzyżowanie i-tej alei i j-tej ulicy możemy opisać jako (i, j). Możesz założyć, że dla dowolnej liczby całkowitej istnieje zarówno ulica jak i aleja z takim numerem.

Bajtazar zaplanował na jutro n dostaw; i-tą dostawę będzie realizował samochód, który wyjedzie z garażu w chwili t_i i pojedzie ulicą lub aleją ze stałą prędkością kilometra na jednostkę czasu. Dostawa może być jednego z dwóch typów: dla dostawy typu pierwszego garaż znajduje się przy skrzyżowaniu (w_i, 0), a samochód jedzie aleją w_i na północ; dla dostawy typu drugiego garaż jest przy skrzyżowaniu (0, w_i), a samochód jedzie ulicą w_i na wschód. Wedle planu z każdego garażu w każdym momencie wyjeżdża co najwyżej jeden samochód.

Samochody nie muszą się zatrzymywać – przejeżdżając obok odpowiednich budynków, kierowcy po prostu wyrzucają pożądaną paczkę. Jest jednak pewien problem – jeśli dwa samochody dostawcze znajdą się w tym samym momencie na tym samym skrzyżowaniu, to zapewne dojdzie do stłuczki. Bajtazar bardzo chciałby tego uniknąć. Niestety, jedyne co może zrobić, to całkowite odwołanie niektórych dostaw. Chciałby zatem wybrać jak najmniej samochodów do odwołania tak, aby spośród pozostałych żadne dwa nie znalazły się w tym samym czasie na tym samym skrzyżowaniu.

입력

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita n (1 ≤ n ≤ 5 · 10⁵), oznaczająca liczbę zaplanowanych dostaw.

W kolejnych n wierszach znajdują się opisy zaplanowanych dostaw; i-ty z tych wierszy składa się z trzech liczb całkowitych r_i, w_i i t_i (r_i ∈ {1, 2}; 1 ≤ w_i ≤ 10⁶; 0 ≤ t_i ≤ 10⁶), oznaczających typ i-tej dostawy, położenie garażu i czas wyjazdu.

출력

Na wyjściu powinna znaleźć się jedna liczba całkowita, oznaczająca minimalną możliwą liczbę dostaw, które należy odwołać.

제한

힌트

Wyjaśnienie przykładu: Próba zrealizowania wszystkich czterech dostaw spowoduje kolizję pierwszego i drugiego samochodu na skrzyżowaniu (5, 3) w chwili 5. Po odwołaniu pierwszej dostawy, nadal będziemy mieli kolizję drugiego i czwartego samochodu na skrzyżowaniu (7, 3) w chwili 7. Z kolei po odwołaniu drugiej dostawy żadne z pozostałych samochodów się nie zderzą.