*Nguồn đề + test: * Free Contest (https://freecontest.net/),

* Đề gốc: * https://drive.google.com/file/d/1N2USUPOOdO7rEyskmAhBYtLcg2fCoaDG/view

*Lời giải: * https://drive.google.com/file/d/1jEnIuv8geT9aYUwzc5CPV4CNl7RW9QRz/view

Một hiệu thuốc bán A loại khẩu trang và B loại dung dịch sát khuẩn. Hộp khẩu trang loại i ~(1 \leq i \leq A)~ có giá ~a_i~, dung dịch sát khuẩn loại j ~(1 \leq j \leq B)~ có giá ~b_j~. Để khuyến khích mọi người đeo khẩu trang và sử dụng dung dịch sát khuẩn để phòng ngừa, ngăn chặn lây lan dịch bệnh Covid-19, cửa hàng quyết định tặng M loại phiếu giảm giá cho khách hàng. Phiếu thứ i sẽ giảm ~c_i~ đồng nếu bạn mua một hộp khẩu trang loại ~x_i~ cùng với một dung dịch sát khuẩn loại ~y_i~.

Hỏi bạn cần ít nhất bao nhiêu để mua một hộp khẩu trang và một dung dịch sát khuẩn. Biết rằng mỗi phiếu giảm giá chỉ sử dụng một lần.

Input

• Dòng đầu tiên gồm ba số nguyên A, B, M ~(1 \leq A, B, M \leq 10^5)~
• Dòng thứ hai gồm A số nguyên ~a_i~ ~(1 \leq a_i \leq 10^5)~ là giá của hộp khẩu trang loại i.
• Dòng thứ ba gồm B số nguyên ~b_j~ ~(1 \leq b_j \leq 10^5)~ là giá của dung dịch sát khuẩn loại i.
• M dòng tiếp theo, dòng thứ i gồm 3 số nguyên ~x_i, y_i, c_i~ ~(1 \leq x_i \leq A, 1 \leq y_i \leq B, c_i \leq a_{x_i}+b_{y_i} )~

Output

• Gồm 1 dòng duy nhất là kết quả bài toán.

Sample Input 1

2 3 1
3 3
3 3 3
1 2 1

Sample Output 1

5

Sample Input 2

1 1 2
10
10
1 1 5
1 1 10

Sample Output 2

10