توجد $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$ |
تم تفعيل تبعيات منطقية بين المهام الفرعية.