#1334. ROUTE - Thiết kế tour du lịch

Sau khi học xong đại học, Nhung làm việc trong công ty du lịch "Sông Hồng" - chuyên tổ chức các tour du lịch ngang qua sông Hồng ở địa phận Hà Nội bằng các tuyến đò ngang giữa các địa điểm hai bên bờ sông. Mỗi địa điểm thực sự là một điểm du lịch hấp dẫn với mức độ hấp dấn được đo bằng số lượng khách du lịch quan tâm tới nó.

Tour du lịch của công ty Sông Hồng bao gồm một dãy liên tiếp các tuyến đò ngang (tức là từ một địa điểm thì địa điểm tiếp theo luôn ở bên kia bờ sông).

Hãy giúp Nhung thiết kế một tour du lịch mà tổng lượng khách quan tâm ở tất cả các địa điểm trên tour là lớn nhất.

Chú ý rằng vì có thể có nhiều tour du lịch đồng thời nên các tuyến đò ngang trong một tour du lịch không cắt nhau. Hai tuyến và cắt nhau nếu và chỉ nếu hoặc hoặc hoặc . Ngoài ra tour du lịch của Nhung có thể bắt đầu và kết thúc ở bất kỳ địa điểm nào.

Dữ liệu vào:

• Dòng đầu tiên ghi ba số lần lượt là số địa điểm ở bờ trái, số địa điểm ở bờ phải và số các tuyến đò ngang.
• dòng tiếp theo, dòng thứ ghi số nguyên là số lượng khách du lịch quan tâm đến địa điểm thứ ở bờ trái;
• dòng tiếp theo, dòng thứ ghi số nguyên là số lượng khách du lịch quan tâm đến địa điểm thứ ở bờ phải;
• dòng cuối cùng, mỗi dòng hai số mô tả một tuyến đò ngang nối địa điểm bên trái với địa điểm bên phải.

Các địa điểm hai bên bờ sông được đánh số từ phía thượng nguồn đến hạ nguồn.

Dữ liệu ra:

• Một số nguyên duy nhất là kết quả tìm được.

Ví dụ:

Dữ liệu vào:

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

Dữ liệu ra:

8