Svada

Ο τοπικός ζωολογικός κήπος έχει αποκτήσει έναν μεγάλο ανοιχτό κήπο στον οποίο τα ζώα μπορούν να κυκλοφορούν ελεύθερα όπως στο φυσικό τους περιβάλλον και διασκεδάζουν τους επισκέπτες με τις συνηθισμένες αταξίες τους.
Τα πιο δημοφιλή ζώα είναι οι μαϊμούδες. Με την αναρρίχηση και το άλμα και άλλες δεξιότητές τους, ξετρελαίνουν τόσο τους μεγάλους όσο και τους νέους επισκέπτες.
Ένα είδος μαϊμούς έχει ειδικευτεί στο σκαρφάλωμα σε ψηλά δέντρα και στο μάζεμα καρύδων. Ένα άλλο είδος έχει ειδικευτεί στο σπάσιμο τους.
Υπάρχουν ~N~ μαϊμούδες του πρώτου είδους (με αριθμούς ~1~ έως ~N~) και ~M~ μαϊμούδες του δεύτερου είδους (με αριθμούς ~1~ έως ~M~).
Η μαϊμού ~k~ του πρώτου είδους χρειάζεται ~A_k~ δευτερόλεπτα για να βρει ένα καλό σημείο στο δέντρο και μετά μαζεύει την πρώτη καρύδα. Μετά από αυτό η μαϊμού παράγει μια νέα καρύδα κάθε ~B_k~ δευτερόλεπτα.
Η μαϊμού ~k~ του δεύτερου είδους χρειάζεται ~C_k~ δευτερόλεπτα για να βρει ένα καλό εργαλείο για το άνοιγμα των καρύδων και μετά ανοίγει την πρώτη του καρύδα. Μετά από αυτό, η μαϊμού ανοίγει άλλη μια καρύδα κάθε ~D_k~ δευτερόλεπτα.
Δυστυχώς, το δεύτερο είδος μαϊμούς είναι εξαιρετικά επιθετικό, επομένως τα δύο είδη δεν μπορούν να είναι μέσα στον κήπο ταυτόχρονα. Επομένως, οι φύλακες του ζωολογικού κήπου θα διώξουν το πρώτο είδος μαϊμούς αμέσως μόλις έχουν μαζέψει όλες τις καρύδες. Ομοίως, εάν οι μαϊμούδες του ίδιου είδους παραμείνουν πολύ ώρα αφού ανοιχτούν όλες οι καρύδες, θα ακολουθήσουν τσακωμοί. Εξαιτίας αυτού, οι φύλακες του ζωολογικού κήπου θα τις διώξουν αμέσως μόλις έχουν ανοίξει όλες τις καρύδες.
Οι φύλακες του ζωολογικού κήπου φτάνουν πρώτα αμέσως μετά τη συλλογή όλων των καρύδων και ξανά αμέσως αφού τις ανοίξουν όλες οι μαϊμούδες. Ο χρόνος που χρειάζεται για να μπουν ή να βγουν οι μαϊμούδες από τον κήπο είναι επίσης αμελητέα μικρός.
Στον Tomislav αρέσει ιδιαίτερα το δεύτερο είδος μαϊμούδων, αλλά δεν μπορεί ποτέ να μαντέψει πότε να φτάσει για να τις δει. Βοηθήστε τον να υπολογίσει την ώρα άφιξης του δεύτερου είδους, αν γνωρίζει τη συνολική ώρα που έκατσαν μαϊμούδες στον κήπο, αλλά δεν ξέρει τον αριθμό των καρύδων στον κήπο.

Είσοδος

Η πρώτη γραμμή περιέχει τον ακέραιο αριθμό ~T (1 \le T \le 1\,000\,000\,000)~, τον συνολικό χρόνο που πέρασαν οι μαϊμούδες στον κήπο, σε δευτερόλεπτα.
Η επόμενη γραμμή περιέχει τον ακέραιο ~N (1 \le N \le 100)~, τον αριθμό των μαϊμούδων του πρώτου είδους.
Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει δύο ακέραιους αριθμούς ~A_k~ και ~B_k (1 \le A_k,\; B_k \le 1\,000\,000\,000)~, πόσο γρήγορη η μαϊμού ~k~ του πρώτου είδους είναι.
Η επόμενη γραμμή περιέχει τον ακέραιο ~M (1 \le M \le 100)~, τον αριθμό των μαϊμούδων του δεύτερου είδους.
Κάθε μία από τις ακόλουθες ~M~ γραμμές περιέχει δύο ακέραιους ~C_k~ και ~D_k (1 \le C_k,\; D_k \le 1\,000\,000\,000)~, πόσο γρήγορη είναι η μαϊμού ~k~ του δεύτερου είδους.

Έξοδος

Τυπώστε τον αριθμό των δευτερολέπτων μεταξύ της άφιξης του πρώτου είδους μαϊμούδων και της άφιξης του δεύτερου είδους.

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

input

12
1
3 1
1
5 1

output

5

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

Στο πρώτο παράδειγμα, αποδεικνύεται ότι υπάρχουν τρεις καρύδες στον κήπο:

• Η μαϊμού του πρώτου είδους μαζεύει την πρώτη καρύδα ~3~ δευτερόλεπτα μετά το άνοιγμα του κήπου.
  
• Η μαϊμού βγάζει τη δεύτερη καρύδα ~4~ δευτερόλεπτα μετά το άνοιγμα του κήπου.
  
• Η μαϊμού βγάζει την τρίτη καρύδα ~5~ δευτερόλεπτα μετά το άνοιγμα του κήπου.
  
• Οι φύλακες του ζωολογικού κήπου μπαίνουν και συνοδεύουν τη μαϊμού έξω. Φτάνει η μαϊμού του δεύτερου είδους. Η έξοδος είναι ~5~ γιατί αυτή είναι η στιγμή που θέλει να φτάσει ο Tomislav.
  
• Η μαϊμού του δεύτερου είδους ανοίγει την πρώτη καρύδα ~10~ δευτερόλεπτα μετά το άνοιγμα του κήπου.
  
• Η μαϊμού ανοίγει τη δεύτερη καρύδα ~11~ δευτερόλεπτα μετά το άνοιγμα του κήπου.
  
• Η μαϊμού ανοίγει την τρίτη καρύδα ~12~ δευτερόλεπτα μετά το άνοιγμα του κήπου.
  
• Οι φύλακες του ζωολογικού κήπου μπαίνουν και συνοδεύουν τη μαϊμού έξω.

input

20
2
3 2
1 3
3
3 1
4 1
5 1

output

13