Tom đang rượt đuổi Jerry qua một ngôi nhà phức tạp. Ngôi nhà được mô hình hóa thành một đồ thị có hướng không chu trình (DAG) gồm \(N\) căn phòng và \(M\) hành lang một chiều kết nối giữa các phòng. Các phòng được đánh số từ \(1\) đến \(N\).

Tại mỗi phòng \(u\), nếu Jerry chạy qua mà kích hoạt bẫy tại phòng đó, Jerry thu được lượng năng lượng là \(A_u\). Ngược lại, nếu không kích hoạt bẫy, Jerry thu được lượng năng lượng là \(B_u\).

Jerry muốn chọn một hành trình di chuyển dọc theo các hành lang một chiều \(p = (v_1, v_2, \dots, v_m)\) (\(m \ge 1\)) kèm theo một tập hợp các phòng được chọn để kích hoạt bẫy \(S \subseteq \{v_1, v_2, \dots, v_m\}\) thỏa mãn các điều kiện sau:

1. Số lượng phòng được kích hoạt bẫy đúng bằng \(K\), tức là \(|S| = K\).
2. Không có hai phòng nào kề nhau liên tiếp trên đường đi cùng được kích hoạt bẫy (để tránh bị sập bẫy liên tiếp). Nghĩa là không tồn tại \(i\) (\(1 \le i < m\)) sao cho cả \(v_i \in S\) và \(v_{i+1} \in S\).

Tổng năng lượng của hành trình \((p, S)\) đạt được là:

Hãy giúp Jerry tìm tổng năng lượng lớn nhất có thể đạt được. Nếu không tồn tại hành trình nào thỏa mãn tất cả các điều kiện trên, in ra \(-1\).

Input

• Dòng đầu tiên chứa ba số nguyên \(N, M, K\) (\(1 \le N \le 30000\), \(1 \le M \le 50000\), \(1 \le K \le 100\)).
• Dòng thứ \(u\) trong \(N\) dòng tiếp theo chứa hai số nguyên \(A_u, B_u\) (\(-10^9 \le A_u, B_u \le 10^9\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) (\(1 \le u, v \le N\), \(u \neq v\)) mô tả một hành trình một chiều từ phòng \(u\) đến phòng \(v\).

Output

• In ra một số nguyên duy nhất là tổng năng lượng lớn nhất thu được. Nếu không tồn tại hành trình hợp lệ, in ra \(-1\).

Example

4 4 2
10 -5
2 100
20 5
3 -1
1 2
1 3
2 4
3 4

113

2 1 2
1 1
1 1
1 2

-1

Scoring

• Subtask 1 (100% điểm): \(1 \le N \le 30000\), \(1 \le M \le 50000\), \(1 \le K \le 100\).

UP VOTE PLS