Zombie Apocalypse

Ο Vito έχει εθιστεί στο νέο δημοφιλές βιντεοπαιχνίδι Zombie Apocalypse. Αυτή τη στιγμή αντιμετωπίζει την εξής πρόκληση: ~m~ ζόμπι κατευθύνονται προς την πόλη και θα της επιτεθούν αν δεν καταφέρει να τα σταματήσει.

Πιο συγκεκριμένα, τα ζόμπι βρίσκονται σε μια μυστική σπηλιά, η οποία απέχει ~n~ μέτρα από την πόλη και βγαίνουν από τη σπηλιά ένα-ένα. Τα ζόμπι περπατούν προς την πόλη με ταχύτητα ~1~ μέτρο ανά δευτερόλεπτο, ενώ υπάρχει παύση ενός δευτερολέπτου μεταξύ της εξόδου δύο διαδοχικών ζόμπι από τη σπηλιά.

Έτσι, μετά το πρώτο δευτερόλεπτο υπάρχει ένα ζόμπι σε απόσταση ~1~ μέτρου από τη σπηλιά· μετά το δεύτερο δευτερόλεπτο υπάρχουν ζόμπι σε αποστάσεις ~1~ και ~2~ μέτρων· μετά το τρίτο δευτερόλεπτο υπάρχουν ζόμπι σε αποστάσεις ~1~, ~2~ και ~3~ μέτρων και ούτω καθεξής. Κάθε φορά που ένα ζόμπι περνάει το ~n~-οστό μέτρο, φτάνει στην πόλη.

Σύμφωνα με τους κανόνες του παιχνιδιού, ο Vito επιτρέπεται να ρίξει ~k~ βόμβες στη διαδρομή μεταξύ της σπηλιάς και της πόλης, προκειμένου να σταματήσει την επίθεση. Για κάθε βόμβα έχει επιλέξει:

• τη θέση (απόσταση από τη σπηλιά) στην οποία θα τοποθετήσει τη βόμβα,
• την ακτίνα της βόμβας, και
• τον χρόνο (σε δευτερόλεπτα) κατά τη ρίψη της βόμβας.

Μια βόμβα με ακτίνα ~r~, τοποθετημένη στη θέση ~x~ τη χρονική στιγμή ~t~, θα εξολοθρεύσει ένα ζόμπι αν αυτό βρίσκεται στη θέση ~y~ τη χρονική στιγμή ~t~, έτσι ώστε η απόσταση μεταξύ των ~x~ και ~y~ να είναι το πολύ ~r~ μέτρα, δηλαδή ~|x - y| \le r~. Τα ζόμπι που έχουν ήδη φτάσει στην πόλη δεν επηρεάζονται από τις βόμβες. Μόλις ένα ζόμπι εξολοθρευτεί, δεν μπορεί πλέον να συνεχίσει την πορεία του προς την πόλη.

Ο Vito μπορεί να επιλέξει τις θέσεις, τις ακτίνες και τους χρόνους ρίψης για τις βόμβες με οποιονδήποτε τρόπο- διαφορετικές βόμβες γίνεται να ριφθούν ταυτόχρονα, ακόμη και στην ίδια θέση.

Δεδομένων των επιλογών του Vito για τις ~k~ βόμβες, να υπολογίσετε πόσα ζόμπι θα φτάσουν στην πόλη.

Είσοδος

Η πρώτη γραμμή περιέχει τρεις φυσικούς αριθμούς ~n~, ~m~ και ~k\;(1 \le n, m, k \le 200)~, οι οποίοι αντιστοιχούν αντίστοιχα στο μήκος, σε μέτρα, της διαδρομής μεταξύ της σπηλιάς και της πόλης, στον αριθμό των ζόμπι και στον αριθμό των βομβών.

Σε καθεμία από τις επόμενες ~k~ γραμμές θα δίνονται τρεις φυσικοί αριθμοί ~x~, ~r~ και ~t\;(1 \le x \le n,\;0 \le r \le n,\; 1 \le t \le 500)~, η απόσταση σε μέτρα, από τη σπηλιά, στην οποία τοποθετείται μία από τις βόμβες, η ακτίνα της συγκεκριμένης βόμβας, σε μέτρα, και η χρονική στιγμή, σε δευτερόλεπτα, κατά την οποία τοποθετείται η βόμβα αντίστοιχα.

Έξοδος

Στην πρώτη και μοναδική γραμμή να εκτυπώσετε έναν αριθμό - τoν αριθμό των ζόμπι που κατάφεραν να φτάσουν στην πόλη.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	13	~m = 1~
2	27	~k = 1~
3	30	Κανένας επιπλέον περιορισμός.

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

input

6 3 3
3 1 2
5 0 7
4 4 8

output

1

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

χρόνος: ~0~, σπηλιά: {~z~, ~z~, ~z~}, διαδρομή: ~(0, 0, 0, 0, 0, 0)~, πόλη: {}

χρόνος: ~1~, σπηλιά: {~z~, ~z~}, διαδρομή: ~(z, 0, 0, 0, 0, 0)~, πόλη: {}

χρόνος: ~2~, σπηλιά: {~z~}, διαδρομή: ~(z, z, 0, 0, 0, 0)~, πόλη: {}

χρόνος: ~2~, σπηλιά: {~z~}, διαδρομή: ~(z, z, 0, 0, 0, 0)~, πόλη: {}

χρόνος: ~2~, σπηλιά: {~z~}, διαδρομή: ~(z, 0, 0, 0, 0, 0)~, πόλη: {}

χρόνος: ~3~, σπηλιά: {}, διαδρομή: ~(z, z, 0, 0, 0, 0)~, πόλη: {}

χρόνος: ~4~, σπηλιά: {}, διαδρομή: ~(0, z, z, 0, 0, 0)~, πόλη: {}

χρόνος: ~5~, σπηλιά: {}, διαδρομή: ~(0, 0, z, z, 0, 0)~, πόλη: {}

χρόνος: ~6~, σπηλιά: {}, διαδρομή: ~(0, 0, 0, z, z, 0)~, πόλη: {}

χρόνος: ~7~, σπηλιά: {}, διαδρομή: ~(0, 0, 0, 0, z, z)~, πόλη: {}

χρόνος: ~7~, σπηλιά: {}, διαδρομή: ~(0, 0, 0, 0, z, z)~, πόλη: {}

χρόνος: ~7~, σπηλιά: {}, διαδρομή: ~(0, 0, 0, 0, 0, z)~, πόλη: {}

χρόνος: ~8~, σπηλιά: {}, διαδρομή: ~(0, 0, 0, 0, 0, 0)~, πόλη: {~z~}

χρόνος: ~8~, σπηλιά: {}, διαδρομή: ~(0, 0, 0, 0, 0, 0)~, πόλη: {~z~}

χρόνος: ~8~, σπηλιά: {}, διαδρομή: ~(0, 0, 0, 0, 0, 0)~, πόλη: {~z~}

input

7 7 1
3 2 6

output

2

input

3 3 1
3 3 3

output

0