Thiết kế tuyến đường

Có $N$ địa điểm ở bờ trái và $M$ địa điểm ở bờ phải của một con sông. Địa điểm $i$ bờ trái có giá trị $A_i$ ($1\le i\le N$), địa điểm $j$ bờ phải có giá trị $B_j$ ($1\le j\le M$). Có $R$ tuyến đường nối các địa điểm bờ trái với bờ phải (không có tuyến nối hai địa điểm cùng bờ).

Một hành trình là một dãy các địa điểm liên kết qua các tuyến đường. Hành trình hợp lệ khi không có hai tuyến đường nào trong hành trình giao nhau. Tuyến $(u_1\leftrightarrow v_1)$ và $(u_2\leftrightarrow v_2)$ giao nhau nếu $u_1<u_2$ và $v_1>v_2$ (hoặc ngược lại).

Tìm hành trình hợp lệ sao cho tổng giá trị các địa điểm trong hành trình là lớn nhất.

Dữ liệu vào

• Dòng 1: Ba số nguyên $N$, $M$, $R$
• Dòng $i+1$ (với $1\le i\le N$): Giá trị $A_i$
• Dòng $N+j+1$ (với $1\le j\le M$): Giá trị $B_j$
• Dòng $N+M+k+1$ (với $1\le k\le R$): Hai số nguyên $u_k$ và $v_k$

Dữ liệu ra

• Một số nguyên duy nhất: tổng giá trị lớn nhất

Ràng buộc

• $1\le N,M\le 40000$
• $0\le R\le 100000$
• $0\le A_i,B_j\le 40000$

Ví dụ