Sau khi thoát khỏi trang trại, Bessie quyết định mở một công ty du lịch dọc theo sông Amoozon. Có một số địa điểm du lịch nằm ở hai bên bờ sông, mỗi địa điểm có một giá trị nguyên biểu thị mức độ thú vị của nó.

Các địa điểm du lịch được nối với nhau bởi những tuyến đường băng qua sông (nghĩa là không có tuyến đường nào nối hai địa điểm ở cùng một bên bờ). Bessie muốn thiết kế một chuyến tham quan cho khách hàng và cần bạn giúp đỡ. Một chuyến tham quan là một dãy các địa điểm du lịch sao cho hai địa điểm kề nhau được nối bởi một tuyến đường. Để phục vụ khách hàng tốt nhất, cô muốn tìm chuyến tham quan làm tối đa tổng giá trị của tất cả các địa điểm được ghé thăm.

Tuy nhiên, Bessie có thể tổ chức nhiều chuyến tham quan như vậy cùng lúc. Vì thế, điều quan trọng là không có hai tuyến đường nào trong một chuyến tham quan giao nhau. Hai tuyến đường \((a \leftrightarrow x)\) và \((b \leftrightarrow y)\) giao nhau khi và chỉ khi một trong các điều kiện sau đúng: \(a < b\) và \(y < x\); \(b < a\) và \(x < y\); hoặc \(a = b\) và \(x = y\).

Hãy giúp Bessie tìm chuyến tham quan tốt nhất cho công ty của cô. Bessie có thể bắt đầu và kết thúc tại bất kỳ địa điểm nào ở bất kỳ bên bờ nào của sông Amoozon.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(N\) (\(1 \le N \le 40\,000\)), \(M\) (\(1 \le M \le 40\,000\)) và \(R\) (\(0 \le R \le 100\,000\)), cách nhau bởi dấu cách, lần lượt biểu thị số địa điểm ở bờ trái, số địa điểm ở bờ phải và số tuyến đường.

\(N\) dòng tiếp theo: dòng thứ \(i+1\) chứa một số nguyên \(L_i\) (\(0 \le L_i \le 40\,000\)), biểu thị giá trị của địa điểm du lịch thứ \(i\) ở bờ trái.

\(M\) dòng tiếp theo: dòng thứ \(i+N+1\) chứa một số nguyên \(R_i\) (\(0 \le R_i \le 40\,000\)), biểu thị giá trị của địa điểm du lịch thứ \(i\) ở bờ phải.

\(R\) dòng tiếp theo: mỗi dòng chứa hai số nguyên \(I\) (\(1 \le I \le N\)) và \(J\) (\(1 \le J \le M\)), cách nhau bởi một dấu cách, cho biết có một tuyến đường hai chiều giữa địa điểm \(I\) ở bờ trái và địa điểm \(J\) ở bờ phải.

Dữ liệu ra

In ra một số nguyên duy nhất cho biết tổng giá trị lớn nhất có thể đạt được trong một chuyến tham quan.

Ví dụ

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

8

Nguồn

USACO 2013 February Contest, Gold — Problem 3: Route Design

Tác giả đề: Yan Gu, 2013.