| Codeforces Round 383 (Div. 1) |
|---|
| Закончено |
Просто напоминаю, некоторые девушки в стране 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.
