ישנן $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$ |
הופעלו תלויות סבירות בין תתי-המשימות.