Go

Ο Branimirko εξακολουθεί να είναι παθιασμένος παίκτης του παγκοσμίου φήμης παιχνιδιού Pokémon Go. Πρόσφατα, αποφάσισε να διοργανώσει έναν διαγωνισμό για να πιάσει Pokémon. Θα διεξαχθεί στην οδό Ilica στο Ζάγκρεμπ και κύριος χορηγός είναι ο φίλος του Slavko. Η ανταμοιβή είναι φυσικά καραμέλες!

Το Ilica είναι, όπως όλοι γνωρίζουμε, ο μεγαλύτερος δρόμος στο Ζάγκρεμπ. Υπάρχουν ~N~ σπίτια στην ίδια πλευρά του δρόμου και κάθε σπίτι έχει έναν αριθμό σπιτιού μεταξύ 1 και ~N~. Ο διαγωνισμός ξεκινά από τον αριθμό του σπιτιού ~K~.

Πριν από τον διαγωνισμό, ο Branimirko κοίταξε τον χάρτη και είδε το ~M~ Pokémon. Κάθε Pokémon βρίσκεται στον (ξεχωριστό) αριθμό του σπιτιού του ~A_i~, αποτιμάται σε ~B_i~ ζαχαρωτά και μπορεί να πιαστεί μόνο στα επόμενα ~T_i~ δευτερόλεπτα, μετά εξαφανίζεται από τον χάρτη και αδύνατο να πιάστει.

Ο Branimirko μπορεί να επισκεφτεί έναν αριθμό σπιτιών ανά δευτερόλεπτο. Επίσης, όταν πιάνει ένα Pokémon, αυτό το Pokémon εξαφανίζεται από τον χάρτη.

Επειδή στον Branimirko του αρέσουν πολύ τα γλυκά, ζήτησε τη βοήθειά σας. Βοηθήστε τον και καθορίστε τη μέγιστη ποσότητα καραμέλας που μπορεί να πάρει!

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει ακέραιους αριθμούς ~N,\;K\;(1 \le K \le N \le 1\,000)~ και ~M\;(1 \le M \le 100)~, τον αριθμό των σπιτιών, τον αριθμό του αρχικού σπιτιού και τον αριθμό των Pokémon.
Κάθε μία από τις ακόλουθες γραμμές ~M~ περιέχει ακέραιους αριθμούς ~A_i\;(1 \le A_i \le N),\;B_i\;(1 \le B_i \le 100)~ και ~T_i\;(1 \le T_i \le 2\,000)~ από την εργασία.
Στα δεδομένα εισόδου, τα Pokémon θα είναι πάντα σε αυστηρά αύξουσα σειρά κατά αριθμό σπιτιού ~A_i~.

Έξοδος

Πρέπει να τυπώσετε την απαιτούμενη μέγιστη ποσότητα καραμελών από την εργασία.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας 20% των συνολικών πόντων, θα ισχύει ~M \le 10~.
Σε επιπλέον 20% των συνολικών πόντων, θα ισχύει ~M \le 20~.

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

input

10 5 4
1 30 4
3 5 7
7 10 12
9 100 23

output

115

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

Μια στρατηγική είναι ότι ο Branimirko πιάνει πρώτα τα Pokémon στο σπίτι νούμερο 3 (5 γλυκά), μετά, αντίστοιχα, τους αριθμούς σπιτιού 7 (10 γλυκά) και 9 (100 γλυκά) για συνολικά 115 γλυκά.
Παρατηρήστε ότι ο Branimirko δεν μπορεί να πιάσει το Pokémon στο σπίτι νούμερο 1, επειδή δεν μπορεί να το φτάσει εγκαίρως από την αρχική του θέση (σπίτι νούμερο 5).

input

20 8 7
1 35 14
4 57 1
6 32 2
9 94 28
14 78 8
15 8 1
17 55 3

output

172