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
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≤
) - 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ố
, (1≤ , ≤ ) - 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ố
, ( 1≤ , ≤ )
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.
Comments
=((