Một cửa hàng 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 \le i \le A\)) có giá \(a_i\), chai dung dịch sát khuẩn loại \(j\ (1 \le j \le 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 một hộp mua khẩu trang loại \(x_i\) cùng với một chai 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 chai dung dịch sát khuẩn. Biết
rằng mỗi phiếu giảm giá chỉ sử dụng được một lần.

Input

• Dòng đầu tiên, gồm ba số nguyên \(A, B, M\).
• Dòng thứ hai, gồm \(A\) số nguyên - số nguyên thứ \(i\) là giá của hộp khẩu trang loại \(i\).
• Dòng thứ ba, gồm \(B\) số nguyên - số nguyên thứ \(j\) là giá của hộp khẩu trang loại \(j\).
• \(M\) dòng tiếp theo, mỗi dòng gồm ba số nguyên \(x_i, y_i, c_i\).

Output

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

Constants

• \(1 \le A, B, M \le 10^5\).
• \(1 \le a_i, b_i, c_i \le 10^5.\)
• \(1 \le x_i \le A\).
• \(1 \le y_i \le B\).
• \(c_i \le a_{x_i} + b_{y_i}\).

Example

2 3 1
3 3
3 3 3
1 2 1

5

1 1 2
10
10
1 1 5
1 1 10

10