Một cửa hàng bán \(N\) loại khẩu trang và \(M\) loại dung dịch sát khuẩn. Hộp khẩu trang loại \(i(1≤i≤N)\) có giá là \(a_i\), chai sát khuẩn loại \(i(1≤i≤M)\) có giá là \(b_i\).

Để 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 \(P\) 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 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\).

Yêu cầu: Cần ít nhất bao nhiêu tiền để 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 chứa 3 số \(N,M,P (1≤N,M,P≤10^5 ).\)

• Dòng thứ 2 chứa \(N\) số nguyên \(a_1,a_2,…,a_N (1≤a_i≤10^5).\)

• Dòng thứ 3 chứa \(M\) số nguyên \(b_1,b_2,…,b_M (1≤b_i≤10^5 ).\)

• Dòng thứ \(i\) trong \(P\) dòng tiếp theo chứa ba số nguyên \(x_i,y_i,c_i (1≤x_i≤N,1≤y_i≤M,1≤c_i≤a_{x_i}+b_{y_i }).\)

Output

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

Sample Input

2 3 1
3 3
3 3 3
1 2 1

Sample Output

5

Sample Input

1 1 2
10
10
1 1 5
1 1 10

Sample Output

10