提醒一下,Arpa 土地上的女孩真的很好。
迈赫达德想要邀请一些霍斯到宫殿参加舞会。每个 Hos 都有一些重量 wi 和一些美观 bi。每个Hos也可能有一些朋友。软管分为一些友谊组。当且仅当存在一系列软管 a1, a2, ..., ak 使得 ai 和 ai + 1 是朋友(每个 1 ≤ i < k,且 a1 = x 且 ak = y)时,两个软管 x 和 y 位于同一友谊组中。
阿尔帕允许使用迈赫达德宫殿的圆形剧场举办这次聚会。阿帕的圆形剧场最多只能承受 w 的重量。
Mehrdad 非常贪婪,他想邀请一些 Hoses,使得它们的权重总和不大于 w,并且它们的美感总和尽可能大。除此之外,他可以从每个友谊小组中邀请所有软管,或者最多邀请一个。否则,某些软管会受到伤害。为 Mehrdad 找到他可以邀请的软管的最大可能总美观,这样就不会有人受伤,并且总重量不超过 w。
输入
第一行包含整数 n、m 和 w (1 ≤ n ≤ 1000, $$0 \leq m \leq \min\left(\frac{n(n-1)}{2}, 10^5\right)$$, 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),这意味着 Hoses xi 和 yi 是朋友。请注意,友谊是双向的。所有对 (xi, yi) 都是不同的。
输出
打印 Mehrdad 可以邀请的软管的最大可能总美丽,以便没有人受伤并且总重量不超过 w。
示例
输入 #1
3 1 5 3 2 5 2 4 2 1 2
输出 #1
6
输入 #2
4 2 11 2 4 6 6 6 4 2 1 1 2 2 3
输出 #2
7
注意
在第一个示例中,有两个友谊组:Hoses {1, 2} 和 Hos {3}。最好的方法是选择第一组中的所有软管,其重量之和等于 5,美观之和为 6。
在第二个示例中,有两个友谊组:Hoses {1,2,3} 和 Hos {4}。 Mehrdad 无法邀请第一组中的所有 Hos,因为它们的总权重为 12 > 11,因此最好的方法是从第一组中选择第一个 Hos,并从第二组中选择唯一一个 Hos。总重量为8,总美度为7。