Autobahn

Υπάρχουν ~N~ άνθρωποι που δοκιμάζουν τα αγωνιστικά τους αυτοκίνητα σε περιβόητους αυτοκινητόδρομους όπου δεν υπάρχουν όρια. Σε αυτό το πρόβλημα ωστόσο υπάρχουν όρια. Σας παρακαλούμε λοιπόν να συγκρατηθείτε από την υποβολή εκθετικής πολυπλοκότητας λύσεων.
Το άτομο που ήρθε στον αυτοκινητόδρομο στην αρχή του λεπτού ~l_i~, πλήρωσε για ~t_i~ λεπτά παραμονής και έφυγε στο τέλος του λεπτού ~r_i~. Δυστυχώς κάποιοι έμειναν για περισσότερο από αυτό που πλήρωσαν. Η διοίκηση του αυτοκινητόδρομου αποφάσισε να μην είναι πολύ σκληρή και να τους χρεώσει μόνο για εκείνα τα επιπλέον λεπτά στα οποία υπήρχαν τουλάχιστον ~K~ άνθρωποι στον αυτοκινητόδρομο.
Σε ένα κύμα γενναιοδωρίας, η διοίκηση αποφάσισε να εισαγάγει happy hour, δηλαδή διάστημα συνεχούς ~X~ λεπτών για τα οποία δεν θα πληρώνουν επιπλέον χρεώσεις. Επέλεξαν το happy hour έτσι ώστε το άθροισμα των επιπλέον χρεώσεων που δεν θα πληρωθούν είναι στο μέγιστο δυνατό. Προσδιορίστε αυτό το άθροισμα.

Είσοδος

Η πρώτη γραμμή περιέχει ακέραιους αριθμούς ~N~ , ~K~ και ~X (K \le N )~ από την περιγραφή του προβλήματος.
Οι επόμενες ~N~ γραμμές περιέχουν ακέραιους αριθμούς ~l_i,\,t_i~ και ~r_i (l_i \le r_i)~ από την περιγραφή του προβλήματος.

Έξοδος

Εκτυπώστε το απαιτούμενο άθροισμα σε μία γραμμή.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	20	~1 \le N, K, X, l_i, t_i, r_i \le 100~
2	30	~1 \le N, K, X, l_i, t_i, r_i \le 1\,000~
3	50	~1 \le N \le 10^5,\,1 \le X, l_i, t_i , r_i \le 10^9~

Παραδείγματα

input

5 3 4
2 1 4
3 3 7
3 3 8
1 5 7
5 3 8

output

7

Επεξήγηση του 1ου πραδείγματος

Το happy hour θα διαρκέσει από το \(4^{ο}\) μέχρι το \(7^{ο}\) λεπτό. Σε αυτό το διάστημα το πρώτο άτομο θα έπρεπε να έχει πληρώσει επιπλέον για το \(4^{ο}\) λεπτό και το δεύτερο, το τρίτο και το τέταρτο άτομο θα έπρεπε να έχουν πληρώσει για το \(6^{ο}\) και \(7^{ο}\) λεπτό.

input

3 2 22
7 16 33
69 14 88
8 10 97

output

27