Alice có ~n~ món đồ cổ và muốn bán tất cả trong ~m~ ngày. Cô đã tìm hiểu và biết được ~c_{it}~ là số tiền mà cô sẽ nhận được nếu bán món đồ ~i~ (~1 \le i \le n~) ở ngày ~t~ (~1 \le t \le m~) hoặc ~c_{it} = -1~ nếu không ai muốn mua món đồ ~i~ ở ngày ~t~. Một số món đồ cổ phát bán trước một số món đồ khác, có ~k~ ràng buộc như vậy, mỗi ràng buộc có dạng ~(u, v)~ và có nghĩa là món đồ ~u~ phải được bán trước ít nhất một ngày so với ngày bán món đồ ~v~. Alice muốn lên kế hoạch bán tối ưu để có thể thu được số tiền lớn nhất. Chú ý rằng, mỗi ngày Alice có thể bán nhiều hơn một món đồ miễn là các món đồ liên quan đến các ràng buộc được thỏa mãn.

Yêu cầu: Giúp Alice tính số tiền nhiều nhất có thể thu được nếu Alice bán được tất cả ~n~ món đồ.

Input

• Dòng đầu tiên ghi ba số nguyên dương ~n, m, k~ (~n, m, k \le 100~);
• Tiếp theo là ~n~ dòng, dòng thứ ~i~ (~1 \le i \le n~) chứa ~m~ số nguyên ~c_{i1}, c_{i2}, ..., c_{im}~ (~-1 \le c_{it} \le 100~);
• Tiếp theo là ~k~ dòng, mỗi dòng chứa hai số nguyên dương ~u, v~ (~1 \le u, v \le n~) cho biết món đồ ~u~ phải trước ít nhất một ngày so với ngày bán món đồ ~v~. Dữ liệu đảm bảo có cách bán hết cả ~n~ món đồ.

Output

Số tiền nhiều nhất có thể thu được trong kế hoạch bán tối ưu tất cả các món đồ.

Sample Input 1

3 2 2
100 -1
100 80
100 90
1 2
1 3

Sample Output 1

270

Subtasks

• Subtask 1 (25 điểm): ~n \le 15~;
• Subtask 2 (35 điểm): Trong ~k~ ràng buộc không có hai ràng buộc nào có cùng giá trị ~v~;
• Subtask 3 (40 điểm): Không có ràng buộc gì thêm.