มีงานทั้งหมด $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$ |
มีการเปิดใช้งานความขึ้นต่อกันของงานย่อยอย่างเหมาะสม