Πρόβλημα S3: Reach for the Top

Ήρθε η ώρα για τον Μπομπ να αντιμετωπίσει τον μεγαλύτερο φόβο του στο Λύκειο H.S.: τη διαβόητη αναρρίχηση με σχοινί στο γυμναστήριο. Σε αυτή τη βάναυση δοκιμασία δύναμης και αντοχής, ο Μπομπ έχει επιφορτιστεί να ανεβεί μέρος του απείρου μήκους κατακόρυφου σχοινιού. Αρχίζει πιάνοντας στο κάτω μέρος του σχοινιού, σε ύψος 0, και πρέπει να φτάσει οποιοδήποτε ύψος ~H~ ~(1 \le H \le 1.000.000)~ ή μεγαλύτερο (μετριέται σε μέτρα).

Σαν να μην έφτανε αυτό, η Αλίκη έκανε φάρσα στον Μπομπ απλώνοντας σκόνη φαγούρας σε ορισμένα τμήματα του σχοινιού, τα οποία θα πρέπει να αποφύγει στην πορεία! Το έχει κάνει για ~N~ ~(0 \le N \le H - 1)~ τμήματα, το ~i~-ο των οποίων καλύπτει όλα τα ύψη από ~A_i~ έως ~B_i~, συμπεριλαμβανομένων ~(1 \le A_i \le B_i \le H - 1)~. Ποτέ δεν επικαλύπτονται δύο τμήματα μεταξύ τους, ακόμη και στα άκρα του.

Το στυλ αναρρίχησης του Μπομπ είναι..., τουλάχιστον, ασυνήθιστο το οποίο μπορεί να είναι χρήσιμο για την αποφυγή της σκόνης φαγούρας της Αλίκης. Σε οποιοδήποτε στιγμή, δεδομένου ότι κρατιέται από το σχοινί σε κάποιο ύψος ~h_1~, μπορεί να εκτελέσει μόνο μία από τις ακόλουθες δύο πιθανές ενέργειες:

1. Πηδάει προς τα πάνω κατά ένα ύψος ακριβώς ~J~ ~(1 \le J \le H)~, έτσι ώστε το νέο του ύψος να είναι ~h_2 = h_1 + J~, αλλά μόνο αν το σχοινί δεν καλύπτεται με σκόνη φαγούρας στο ύψος ~h_2~.
2. Πέφτει προς τα κάτω κατά οποιοδήποτε ύψος, έτσι ώστε το νέο του ύψος να είναι οποιοσδήποτε ακέραιος αριθμός ~h_2~ ~(0 \le h_2 < h_1 )~, αλλά μόνο εάν το σχοινί δεν καλύπτεται με σκόνη φαγούρας στο ύψος ~h_2~.

Και οι δύο τύποι ενεργειών που εμπλέκονται σε αυτήν την τεχνική είναι, ευνοήτως, αρκετά κουραστικοί, οπότε ο Μπομπ θα ήθελε να αποφύγει να εκτελέσει περισσότερες από αυτές που χρειάζονται. Βοηθήστε τον να καθορίσει τον ελάχιστο αριθμό ενεργειών που πρέπει να εκτελέσει για να φτάσει σε ύψος τουλάχιστον \(Η\) μέτρων ή να καθορίσει ότι είναι δυστυχώς αδύνατο για αυτόν να φτάσει ποτέ σε τέτοιο ύψος.

Υποπροβλήματα

Σε δοκιμαστικές περιπτώσεις αξίας 8/27 των πόντων, ~H \le 1000~ και ~J \le 2~.
Σε δοκιμαστικές περιπτώσεις αξίας επιπλέων 12/27 των πόντων, ~H \le 1000~.

Είσοδος

Η πρώτη γραμμή εισόδου αποτελείται από τρεις ακέραιους που χωρίζονται με κενό, ~H~, ~J~ και ~N~.
Ακολουθούν ~N~ γραμμές, η ~i~-η των οποίων αποτελείται από δύο χωρισμένους ακέραιους αριθμούς, ~A_i~ και ~B_i~, για ~i = 1\ldots N~.

Έξοδος

Εξαγάγετε έναν μόνο ακέραιο αριθμό, είτε τον ελάχιστο αριθμό ενεργειών που απαιτούνται για να φτάσει ο Μπομπ σε ύψος τουλάχιστον ~H~ μέτρων, ή -1 εάν είναι αδύνατο να το κάνει.

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

1ο

input

12 5 2
2 4
10 10

output

5

Επεξήγηση Παραδείγματος:
Στην πρώτη περίπτωση, ο Μπομπ μπορεί να πηδήξει σε ύψος 5, να πέσει σε ύψος 1, να πηδήξει σε ύψος 6, να πηδήξει επάνω σε ύψος 11, και τελικά να κάνει άλμα μέχρι ύψος 16. Αυτή είναι η μόνη στρατηγική που περιλαμβάνει 5 ενέργειες, οι οποίος είναι ο ελάχιστος δυνατός αριθμός ενεργειών.

2o

input

5 2 2
1 1
4 4

output

-1

Επεξήγηση Παραδείγματος:
Στη δεύτερη περίπτωση, ο Μπομπ πρέπει να ξεκινήσει πηδώντας σε ύψος 2. Από εκεί, δεν μπορεί να πηδήξει προς τα πάνω σε ύψος 4 (καθώς το σχοινί είναι καλυμμένο με σκόνη φαγούρας σε εκείνο το τμήμα), και ομοίως δεν μπορεί να πέσει σε ύψος 1, που σημαίνει ότι δεν μπορεί ποτέ να πιάσει το σχοινί σε οποιοδήποτε ύψος εκτός από το 0 ή το 2.