Một cửa hàng đồ chơi mới nhập về \(n\) chiếc ô tô và \(n\) bộ xếp hình mới, \(n\) chiếc ô tô được trưng bày thành một hàng ngang và được đánh số từ \(1\) tới \(n\) từ trái qua phải, tương tự, \(n\) bộ xếp hình cũng được trưng bày thành một hàng ngang và được đánh số từ \(1\) tới \(n\) từ trái qua phải. Giá của chiếc ô tô thứ \(i\) (\(1 \le i \le n\)) là \(a_i\) đồng, giá của bộ xếp hình thứ \(j\) (\(1 \le j \le n\)) là \(b_j\) đồng.

Trường mẫu giáo XYZ quyết định mua ô tô và bộ xếp hình từ cửa hàng đồ chơi để làm phong phú thêm kho đồ chơi của nhà trường. Sau khi thực hiện khảo sát đối với \(m\) trẻ trong trường, nhà trường biết rằng trẻ thứ \(k\) (\(1 \le k \le m\)) rất thích chiếc ô tô \(x_k\) (\(1 \le x_k \le n\)) hoặc bộ xếp hình \(y_k\) (\(1 \le y_k \le n\)). Tuy nhiên, cửa hàng đồ chơi chỉ đồng ý bán cho nhà trường những chiếc ô tô nằm liên tiếp trong hàng và những bộ xếp hình nằm liên tiếp trong hàng.

Yêu cầu: Hãy xác định số tiền ít nhất để mua đồ chơi mà trẻ nào cũng có món đồ chơi mình thích.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) là số lượng ô tô và số lượng bộ xếp hình.
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,a_2,...,a_n\) (\(a_i \le 10^9\)) là giá của \(n\) chiếc ô tô.
• Dòng thứ ba chứa \(n\) số nguyên dương \(b_1,b_2,...,b_n\) (\(b_i \le 10^9\)) là giá của \(n\) bộ xếp hình.
• Dòng thứ tư chứa số nguyên dương \(m\) là số lượng trẻ của trường mẫu giáo.
• Tiếp theo là \(m\) dòng, dòng thứ \(k\) (\(1 \le k \le m\)) chứa hai số nguyên dương \(x_k\) và \(y_k\) (\(1 \le x_k,y_k \le n\)).

Output

• Một số là số tiền ít nhất để mua đồ chơi thỏa mãn yêu cầu.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n \le 10, m \le 10\).
• Subtask \(2\) (\(10\%\) số điểm): \(n \le 100, m \le 2 \times 10^5\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 500, m \le 2 \times 10^5\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 2000, m \le 2 \times 10^5\).
• Subtask \(5\) (\(40\%\) số điểm): \(n \le 2 \times 10^5, m \le 2 \times 10^5\).

Example

4
9 1 1 9
9 9 9 1
3
2 1
3 1
4 4

3

4
1 1 1 1
6 7 8 9
3
1 2
2 2
3 2

3