← 返回题目列表

Codeforces · 741/B

B. 阿尔帕薄弱的圆形剧场和迈赫达德宝贵的软管

中文机器翻译题面 查看原题

提醒一下,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。