Double Attendance

Χάρη στο ιδιαίτερα φιλόδοξο σχολικό πρόγραμμα, δύο από τα μαθήματά σας πρόκειται να ξεκινήσουν την ίδια ακριβώς ώρα, σε δύο διαφορετικές τάξεις! Εσείς μπορείτε να είστε μόνο σε ένα μέρος τη φορά, οπότε στην καλύτερη περίπτωση ελπίζετε να μπορέσετε να προλάβετε τα σημαντικά μέρη από τα δύο μαθήματα, ακόμα και αν αυτό σημαίνει ότι πρέπει να πηγαινοέρχεστε ανάμεσα στα μαθήματα.

Οι δύο τάξεις είναι αριθμημένες ~1~ και ~2~. Στην τάξη ~i~, ο δάσκαλος θα δείξει ~N_i~ διαφορετικές διαφάνειες κατά την διάρκεια του μαθήματος, με την ~j~-οστη διαφάνεια να δείχνεται σε όλη τη διάρκεια του αποκλειστικού χρονικού διαστήματος ~(A_{i,j}, B_{i,j})~ ~(0 \le A_{i,j} < B_{i,j})~ όπου ~A_{i,j}~ και ~B_{i,j}~ είναι ο χρόνος που πέρασε από την αρχή του μαθήματος μετρημένος σε δευτερόλεπτα. Και στα δύο μαθήματα, δεν υπάρχει κάποια χρονική στιγμή στην οποία να δείχνονται πολλαπλές διαφάνειες ταυτόχρονα. Για παράδειγμα, ένα μάθημα μπορεί να έχει διαφάνειες που εκτείνονται στο ζεύγος των διαστημάτων ~(1, 2)~ και ~(5, 6)~, ή στο ζεύγος ~(10, 20)~ και ~(20, 30)~, αλλά όχι το ζεύγος ~(10,20)~ και ~(19,30)~.

Ξεκινάτε την μέρα σας στην τάξη ~1~, με τα δύο μαθήματα να ξεκινούν την χρονική στιγμή ~0~. Έπειτα, σε οποιαδήποτε χρονική στιγμή (όχι απαραίτητα μετά από ακέραιο αριθμό δευτερολέπτων), μπορείτε να μεταβείτε από την τρέχουσα τάξη σε μια άλλη σε ~K~ δευτερόλεπτα. Θεωρείται ότι έχετε δει μια διαφάνεια αν περάσετε ένα θετικό χρονικό διάστημα στην τάξη στην οποία παρουσιάζεται η διαφάνεια αυστηρά εντός του χρονικού διαστήματος στο οποίο εμφανίζεται. Όταν μετακινείστε ανάμεσα στις τάξεις, θεωρείται πως δεν βρίσκεστε μέσα σε καμία από τις δύο τάξεις για ~K~ δευτερόλεπτα και επομένως δεν μπορείτε να δείτε καμία διαφάνεια.

Για παράδειγμα, αν η τάξη ~1~ έχει μια διαφάνεια η οποία παρουσιάζεται το χρονικό διάστημα ~(10, 20)~, η τάξη ~2~ έχει μια διαφάνεια που παρουσιάζεται το διάστημα ~(15, 25)~ και ~K = 8~, τότε θα μπορέσετε να δείτε και τις δύο διαφάνειες αν φύγετε από την τάξη ~1~ προς την τάξη ~2~ την χρονική στιγμή ~11.5~ ~sec~ (φτάνοντας την χρονική στιγμή ~19.5~ ~sec~). Από την άλλη, αν φύγετε από την τάξη ~1~ την χρονική στιγμή ~17~ ~sec~ (φτάνοντας την χρονική στιγμή ~25~ ~sec~), τότε θα μπείτε στην τάξη ~2~ αμέσως μόλις σταματήσει να παρουσιάζεται η διαφάνεια και επομένως θα την χάσετε.

Ποιός είναι ο μέγιστος αριθμός ξεχωριστών διαφανειών που μπορείτε να δείτε έστω μια φορά;

Είσοδος

Η πρώτη γραμμή περιέχει τρεις, χωρισμένους με κενό, ακέραιους ~N_1~, ~N_2~ και ~K~.

Οι επόμενες ~N_1~ γραμμές περιέχουν η καθεμία δύο, χωρισμένους με κενό, ακέραιους ~A_{1,i}~ και ~B_{1,i}~ ~(1 \le i \le N_1)~.

Οι επόμενες ~N_2~ γραμμές περιέχουν η καθεμία δύο, χωρισμένους με κενό, ακέραιους ~A_{2,i}~ και ~B_{2,i}~ ~(1 \le i \le N_2)~.

Βαθμολογία

Βαθμοί	Περιορισμοί στο ~N_i~	Περιορισμοί στο ~A_{i,j}~ και ~B_{i,j}~	Περιορισμοί στο ~K~
5	~1 \le N_i \le 10~	~0 \le A_{i,j} < B_{i,j} \le 2\,000~	~1 \le K \le 10^9~
10	~1 \le N_i \le 2\,000~	~0 \le A_{i,j} < B_{i,j} \le 2\,000~	~1 \le K \le 10^9~
6	~1 \le N_i \le 2\,000~	~0 \le A_{i,j} < B_{i,j} \le 2\,000~ ~B_{i,j} - A_{i,j} \le 2K~	~1 \le K \le 10^9~
4	~1 \le N_i \le 300\,000~	~0 \le A_{i,j} < B_{i,j} \le 10^9~	~1 \le K \le 10^9~

Έξοδος

Εκτυπώστε έναν ακέραιο, ο οποίος είναι ο μέγιστος αριθμός ξεχωριστών διαφανειών που μπορείτε να δείτε.

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

input

3 1 8
10 20
100 101
20 21
15 25

output

3

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

Μια πιθανή βέλτιστη στρατηγική είναι να παραμείνετε στη τάξη ~1~ μέχρι την χρονική στιγμή ~11.5~, έπειτα να πάτε στην τάξη ~2~ (φτάνοντας την χρονική στιγμή ~19.5~), να παραμείνετε εκεί μέχρι την χρονική στιγμή ~19.6~ και τέλος να επιστρέψετε στην τάξη ~1~ (φτάνοντας την χρονική στιγμή ~27.6~). Με αυτό τον τρόπο θα δείτε όλες τις διαφάνειες εκτός της 3ης. Είναι αδύνατον να δείτε και τις 4 διαφάνειες.

Παράδειγμα 2^o

input

1 5 3
1 100
1 2
2 3
3 4
4 5
5 6

output

4

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

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