Mehrad muốn mời một số thiếu nữ đến cung điện để tham gia buổi khiêu vũ. Mỗi thiếu nữ có cân nặng là ~ w_i ~ và vẻ đẹp là ~ b_i ~. Mỗi thiếu nữ cũng có thể có vài người bạn của riêng họ. Những thiếu nữ được chia thành từng nhóm bạn. Thiếu nữ ~ x ~ và thiếu nữ ~ y ~ được chia vào cùng một nhóm khi và chỉ khi tồn tại ~( a_1, a_2, …, a_k ~ mà ~ a_i ~ và ~ a_{i+1} ~ là bạn ~ ( 1 ≤  i < k ), a_1 = x, a_k = y ~.

Arpa cho phép Mehrad sử dụng giảng đường hoàng gia để tổ chức bữa tiệc. Giảng đường này chỉ chịu được cân nặng tối đa là ~ w ~.

Merhad tham lam đến mức anh muốn mời các thiếu nữ mà cân nặng của họ không vượt quá ~ w ~ và vẻ đẹp của họ đạt lớn nhất. Tuy vậy, với nhóm bạn, Merhad chỉ có thể mời cả nhóm hoặc không mời quá 1 người. Nếu không, những thiếu nữ khác có thể sẽ bị tổn thương. Hãy giúp Merhad tìm vẻ đẹp lớn nhất của các thiếu nữ mà anh ta có thể mời mà không làm thiếu nữ nào tổn thương và cân nặng của họ không vượt quá ~ w ~.

Dữ liệu vào

• Dòng đầu tiên nhập vào các số ~ n, m, w ~ - số thiếu nữ, số cặp tình bạn và cân nặng tối đa mà giảng đường chịu được. ~ ( 1 ≤ n ≤ 1000, 0 ≤ m ≤ min⁡(n(n-1)/2, 10^5 ) , 1 ≤ w ≤ 1000 ) ~.
• Dòng thứ hai nhập vào ~ n ~ số ~ w_1, w_2, …, w_n ~ ~ ( 1 ≤ w_i ≤ 1000 ) ~ - cân nặng của mỗi thiếu nữ.
• Dòng thứ ba nhập vào ~ n ~ số ~ b_1, b_2, …, b_n ~ ~ ( 1 ≤ b_i ≤ 10^6 ) ~ - vẻ đẹp của mỗi thiếu nữ.
• ~ m ~ dòng tiếp theo là các cặp tình bạn, dòng thứ ~ i ~ chứa cặp số nguyên ~ x_i ~ và ~ y_i ~ ~ (1 ≤ x_i, y_i ≤ n, x_i ≠ y_i) ~, ~ x_i ~ và ~ y_i ~ là bạn. Lưu ý rằng ~ A ~ là bạn ~ B ~ thì ~ B ~ cũng là bạn ~ A ~, các cặp bạn đôi một khác nhau.

Kết quả

In ra vẻ đẹp tối đa có thể của các thiếu nữ mà Mehrdad có thể mời để không ai bị tổn thương và tổng trọng lượng không vượt quá ~ w ~.

Ví dụ:

Input 1

3 1 5 
3 2 5 
2 4 2 
1 2 

Output 1

6 

Input 2

4 2 11
2 4 6 6
6 4 2 1
1 2
2 3 

Output 2

7