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 là \(c_{it}\) số tiền mà cô sẽ nhận được nếu bán món đồ \(i\) \((1 \leq i \leq n)\) ở ngày \(t\) \((1 \leq t \leq 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 đồ phải được 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 nhiều tiề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 ràng buộc bán trước các món đồ này đều đã được bán ở các ngày trước.

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

Input

• Dòng đầu tiên ghi ba số nguyên dương \(n, m, k\) \((n, m, k \leq 100)\).
• Tiếp theo là \(n\) dòng, dòng thứ \(i\) \((1 \leq i \leq n)\) chứa \(m\) số nguyên \(c_{i1}, c_{i2}, \ldots, c_{im}\) \((-1 \leq c_{it} \leq 100)\).
• Tiếp theo là dòng \(k\), mỗi dòng chứa hai số nguyên dương \(u, v\) \((1 \leq u, v \leq n)\) cho biết món đồ phải \(u\) 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

• Ghi ra một dòng là số tiền nhiều nhất có thể nhận được khi bán tối ưu tất cả các món đồ.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \leq 15\).
• Subtask \(2\) (\(35\%\) số đ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\%\) số điểm): Không có ràng buộc gì thêm.

Example

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

270