Ngày mai là Ngày của Mẹ, các bạn nhỏ trong tổ Tin học đang vừa học vừa nghĩ xem nên tặng món quà gì cho mẹ để thể hiện tấm lòng của mình.

Nghe nói có một trang web bán những đám mây, họ quyết định cùng nhau lên xem thử món hàng kỳ lạ này.

Cửa hàng có tất cả \(n\) đám mây, được đánh số từ \(1\) đến \(n\). Mỗi đám mây có một giá tiền và một giá trị.

Tuy nhiên, chủ cửa hàng là một người rất lập dị. Ông ta yêu cầu rằng một số đám mây phải được mua cùng nhau - nghĩa là nếu bạn muốn mua một đám mây nào đó, bạn buộc phải mua thêm các đám mây đi kèm với nó.

Là thành viên tổ Tin học, bạn thấy món quà này thật thú vị. Tuy nhiên, vì tiền có hạn, bạn muốn sử dụng số tiền đang có để mua được tổng giá trị đám mây là lớn nhất.

Dữ liệu vào

• Dòng đầu gồm ba số nguyên: \(n\), \(m\), \(w\):
• \(n\) - số lượng đám mây (\(1 \le n \le 10^4\)),
• \(m\) - số cặp đám mây đi kèm nhau (\(0 \le m \le 5000\)),
• \(w\) - số tiền bạn hiện có (\(1 \le w \le 10^4\)).
• Dòng thứ \(2\) đến dòng thứ \(n+1\), mỗi dòng chứa hai số nguyên \(c_i\), \(d_i\):
• \(c_i\) - giá của đám mây thứ \(i\),
• \(d_i\) - giá trị của đám mây thứ \(i\).
• Dòng thứ \(n+2\) đến dòng thứ \(n+1+m\): mỗi dòng gồm hai số nguyên \(u_i\), \(v_i\), biểu thị rằng:
• Nếu mua đám mây \(u_i\) thì bắt buộc phải mua cả đám \(v_i\), và ngược lại.

Dữ liệu ra

• Một dòng duy nhất - giá trị lớn nhất có thể đạt được với số tiền hiện có.

Giới hạn dữ liệu

• Với \(30\%\) dữ liệu: \(1 \le n \le 100\)
• Với \(50\%\) dữ liệu: \(1 \le n, w \le 10^3\), \(1 \le m \le 100\)
• Với \(100\%\) dữ liệu: như phần đầu đã mô tả.

Input 1

5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2

Output 1

1

Giải thích ví dụ

• Có các nhóm bắt buộc mua cùng nhau:
• Nhóm 1: gồm mây 1, 2, 3 - tổng giá: \(3+3+3=9\), tổng giá trị: \(10+10+10=30\)
• Nhóm 2: gồm mây 4, 2 - tổng giá: \(5+3=8\), tổng giá trị: \(100+10=110\)
• Mây 5 riêng lẻ - giá: \(10\), giá trị: \(1\)

Do mây 2 thuộc cả hai nhóm nên nhóm 1 và 2 gộp lại thành một nhóm lớn chứa mây 1, 2, 3, 4 - giá: \(3+3+3+5=14\), vượt quá ngân sách \(10\).

Chỉ có thể chọn mây 5 (giá 10) - được 1 điểm giá trị.