Để chuẩn bị cho vòng chung kết cuộc thi công nghệ trẻ châu Á (YTAC), hai kỹ sư công nghệ là TrQuocAnn và ledinhbaonam đang phải thiết lập một hệ thống siêu máy chủ giả lập.

Hệ thống gồm \(N\) máy chủ. Máy chủ thứ \(i\) tiêu thụ \(w_i\) mức năng lượng và cung cấp \(v_i\) sức mạnh xử lý.

Quá trình đấu nối phần cứng đã tạo ra \(M\) đường cáp quang liên kết. Hai máy chủ được kết nối trực tiếp với nhau sẽ tự động đồng bộ dữ liệu. Tính đồng bộ có tính bắc cầu: nếu máy A đồng bộ với B, và B đồng bộ với C, thì A cũng đồng bộ với C.

Các máy chủ đồng bộ với nhau tạo thành một Cụm máy chủ.

ledinhbaonam là người nắm giữ bộ nguồn điện tổng của hệ thống, có dung lượng tối đa là \(W\).

Theo quy tắc an toàn của mạch điện, với mỗi Cụm máy chủ, hệ thống chỉ được phép chọn đúng một trong ba phương án hoạt động:

• Bật đúng 1 máy chủ bất kỳ trong cụm.
• Bật tất cả các máy chủ trong cụm.
• Không bật máy chủ nào trong cụm đó.

Yêu cầu

Hãy giúp TrQuocAnn tính tổng sức mạnh xử lý lớn nhất mà hệ thống có thể đạt được mà không vượt quá giới hạn năng lượng \(W\).

Input

• Dòng đầu chứa ba số nguyên \(N, M, W\) (\(1 \le N \le 1000\), \(0 \le M \le 100000\), \(0 \le W \le 1000\))
• Dòng thứ hai chứa \(N\) số nguyên \(w_1, w_2, \dots, w_N\) (\(1 \le w_i \le 1000\))
• Dòng thứ ba chứa \(N\) số nguyên \(v_1, v_2, \dots, v_N\) (\(1 \le v_i \le 10^6\))
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x, y\) (\(1 \le x, y \le N,\ x \ne y\))

Output

• In ra một số nguyên duy nhất là tổng sức mạnh xử lý lớn nhất có thể đạt được.

Example

5 3 10
2 3 4 2 2
3 5 8 3 4
1 2
2 3
4 5

16

Scoring

• Subtask 1 (30% số điểm): \(N \le 20\), \(M \le 20\), \(W \le 100\)

• Subtask 2 (30% số điểm): \(M = 0\)

• Subtask 3 (40% số điểm): Không có ràng buộc nào thêm.