Có một khu vườn rộng nằm ngay bên cạnh một sở thú, ở đó có rất nhiều dừa. Sở thú đã huấn luyện được 2 loại khỉ đặc biệt: Loại thứ nhất có khả năng hái dừa và loại thứ hai có khả năng bổ những quả dừa để chế biến thành sản phẩm (nước, cùi,...). Có N con khỉ thuộc loại thứ nhất, con khỉ thứ k của loại này sẽ mất ~A_k~ thời gian để leo lên cây và bắt đầu hái quả dừa đầu tiên. Cứ sau mỗi Bk giây nó hái được một quả.Có M con khỉ thuộc loại thứ hai, con khỉ thứ k của loại này sẽ mất Ck thời gian để tìm công cụ và bắt đầu chế biến quả dừa đầu tiên, cứ sau Dk giây nó chế biến xong một quả dừa. Loại khỉ thứ hai là loại khỉ rất hung hãn nên cúng sẽ đuổi đánh loại khỉ thứ nhất nếu như cùng ở trong vườn tại một thời điểm. Chính vì vậy, đầu tiên người ta cho các con khỉ loại thứ nhất vào hái dừa. Sau khi hái hết những quả dừa, người ta mới đưa con khỉ loại thứ hai vào để chế biến. Thời gian đưa các con khỉ vào/ra khỏi vườn xem như bằng 0. Chúng ta không biết trong vườn có bao nhiêu quả dừa. Tuy nhiên biết rằng T giây là thời gian kể từ khi đưa những con khỉ thứ nhất vào vườn đến khi số dừa được chế biến hoàn toàn.

Hãy xác định sau thời gian bao nhiêu lâu, kể từ khi đưa những con khỉ thứ nhất vào hái dừa đến khi những con khỉ thứ hai được đưa vào vườn.

Input:

• Dòng đầu tiên ghi T là tổng thời gian hai loại khỉ ở trong vườn (1≤T≤~10^9~)
• Dòng thứ hai ghi số nguyên dương N (1≤N≤100)
• N dòng tiếp theo, mỗi dòng ghi hai số ~A_k~, ~B_k~ (1≤~A_k~,~B_k~≤~10^9~)
• Dòng tiếp theo ghi số nguyên dương M (1≤M≤100)
• M dòng cuối, mỗi dòng ghi hai số ~C_k~, ~D_k~( 1≤~C_k~,~D_k~≤~10^9~)

Output: Một số nguyên là khoảng thời gian từ khi đưa con khỉ thứ nhất đến vườn đến khi đưa con khỉ thứ hai đến vườn

Example:

Input

12
1
3 1
1
5 1

Output:

5

Giải thích: Trong vườn có 3 quả dừa

• Ở giây thứ 3 bắt đầu hái quả dừa đầu tiên
• Ở giây 4, 5 hái các quả dừa thứ 2 và thứ 3
• Sau 5 giây đưa loại khỉ thứ hai vào vườn
• Ở giây thứ 10 bắt đầu chế biến quả dừa đầu tiên
• Ở giây 11, 12 bắt đầu chế biến quả dừa thứ 2 và thứ 4
• Sau 12 giây đưa con khỉ thứ hai ra khỏi vườn.