Það eru $n$ verkefni. Verkefni $i$ þarf að taka einn reit á bilinu $[l_i,r_i]$. Ef númer reitsins sem tekinn er uppfyllir $\le t_i$, þá fæst aukaverðlaun upp á $1$. Finndu hámarksverðlaun sem hægt er að fá að því gefnu að öllum verkefnum sé lokið.
Inntak
Ein lína með tveimur heiltölum $n,m$, sem tákna fjölda verkefna og fjölda reita.
Næstu $n$ línur innihalda þrjár heiltölur $l,r,t$ í hverri línu sem lýsa einu verkefni.
Úttak
Ef ómögulegt er að ljúka öllum verkefnum skal prenta $-1$, annars skal prenta svarið.
Dæmi
Inntak 1
3 3 1 2 1 1 2 1 2 3 2
Úttak 1
1
Skýring
Með því að úthluta verkefnunum í röð á reiti $1,2,3$ sést að eitt verkefni fær verðlaun.
Takmarkanir
Fyrir öll prófunargögn gildir $1\le n,m\le 5\times 10^5, 1\le l_i \le t_i \le r_i \le m$.
| Undirverkefni | Stig | Sérstakar takmarkanir |
|---|---|---|
| $1$ | $3$ | $n,m \le 15$ |
| $2$ | $12$ | Öll $l_i$ eru jöfn |
| $3$ | $3$ | Öll $t_i$ eru jöfn |
| $4$ | $19$ | $n,m \le 500$ |
| $5$ | $20$ | $n,m \le 2000$ |
| $6$ | $21$ | $n,m \le 10^5$ |
| $7$ | $22$ | $n,m \le 5\times 10^5$ |
Eðlileg tengsl milli undirverkefna eru virk.