B. Хрупкий амфитеатр Arpa и ценные девушки Mehrdad
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Просто напоминаю, некоторые девушки в стране Arpa по-настоящему красивы.

Mehrdad хочет пригласить некоторых девушек во дворец на танцы. У каждой девушки есть некоторый вес wi и некоторая красота bi. Также, у каждой девушки могут быть друзья среди других девушек. Девушек можно разделить на группы по дружбе. Две девушки x и y находятся в одной группе по дружбе, если и только если существует последовательность девушек a1, a2, ..., ak такая, что ai дружит с ai + 1 для каждого 1 ≤ i < k, а a1 = x и ak = y.

Arpa предоставил амфитеатр для вечеринки Mehrdad. Амфитеатр может выдержать суммарный вес не более w.

Mehrdad настолько жадный, что хочет пригласить некоторых девушек так, чтобы их суммарный вес не превышал w, а их суммарная красота была максимальна. При этом, из каждой группы по дружбе он может пригласить либо всех девушек, либо не более одной, иначе кто-нибудь обидится. Найдите для Mehrdad наибольшую суммарную красоту девушек, которых он может пригласить так, чтобы никто не обиделся, а суммарный вес не превысил w.

Входные данные

Первая строка содержит три целых числа n, m и w (1  ≤  n  ≤  1000, , 1 ≤ w ≤ 1000) — количество девушек, количество пар друзей среди них и максимальный суммарный вес приглашенных.

Вторая строка содержит n целых чисел w1, w2, ..., wn (1 ≤ wi ≤ 1000) — веса девушек.

Третья строка содержит n целых чисел b1, b2, ..., bn (1 ≤ bi ≤ 106) — красоты девушек.

Следующие m строк содержат пары друзей, i-я из этих строк содержит два целых числа xi и yi (1 ≤ xi, yi ≤ n, xi ≠ yi), означающих, что девушка xi дружит с девушкой yi. Заметьте, что дружба обоюдная. Все пары (xi, yi) различны.

Выходные данные

Выведите наибольшую суммарную красоту девушек, которых Mehrdad может пригласить так, чтобы никто не обиделся, а суммарный вес не превысил w.

Примеры
Входные данные
3 1 5
3 2 5
2 4 2
1 2
Выходные данные
6
Входные данные
4 2 11
2 4 6 6
6 4 2 1
1 2
2 3
Выходные данные
7
Примечание

В первом тесте из условия две группы по дружбе: девушки {1, 2}, а также девушка {3}. Лучший способ — пригласить всех девушек из первой группы, их суммарный вес будет равен 5, а суммарная красота — 6.

Во втором тесте из условия также две группы по дружбе: девушки {1, 2, 3}, и девушка {4}. Mehrdad не может пригласить всех девушек из первой группы, т. к. их суммарный вес 12 > 11, поэтому лучше всего пригласить первую девушку из первой группы, и единственную девушку из второй. Суммарный вес будет равен 8, а суммарная красота — 7.