$n$ тапсырма бар, $i$-ші тапсырма $[l_i,r_i]$ аралығындағы бір ұяшықты иеленуі керек. Егер иеленген ұяшықтың нөмірі $\le t_i$ болса, қосымша $1$ сыйақы беріледі. Барлық тапсырма орындалған жағдайда алуға болатын ең көп сыйақыны табыңыз.
Кіріс деректер
Бірінші жолда екі бүтін сан $n,m$ берілген — сәйкесінше тапсырмалар саны мен ұяшықтар саны.
Келесі $n$ жолдың әрқайсысында бір тапсырманы сипаттайтын үш бүтін сан $l,r,t$ берілген.
Шығыс деректер
Егер барлық тапсырманы орындау мүмкін болмаса, $-1$ шығарыңыз, әйтпесе жауапты шығарыңыз.
Мысалдар
Кіріс 1
3 3 1 2 1 1 2 1 2 3 2
Шығыс 1
1
Ескертпе
Тапсырмаларды ретімен $1,2,3$ ұяшықтарына бөлсек, бір тапсырма сыйақы алатыны белгілі болады.
Шектеулер
Барлық деректер үшін $1\le n,m\le 5\times 10^5, 1\le l_i \le t_i \le r_i \le m$ шарты орындалады.
| Ішкі тапсырма | Ұпай | Арнайы шектеулер |
|---|---|---|
| $1$ | $3$ | $n,m \le 15$ |
| $2$ | $12$ | Барлық $l_i$ өзара тең |
| $3$ | $3$ | Барлық $t_i$ өзара тең |
| $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$ |
Ішкі тапсырмалар арасындағы орынды тәуелділіктер қосылған.