题目描述Description

在地球的隔壁，有一颗 lucky 星，上面有 n 个岛屿、m 座桥，每座桥都连接两个岛屿，每次你到达了一个岛屿，你可以获得该岛屿的一张邮票。每个岛屿都属于某一个联邦，如果两个岛屿能通过若干座桥连通，那么它们就属于同一个联邦。

为了探索 lucky 星，地球这边发出悬赏，每个岛屿 i 有 a_{i} 的赏金，当收集到某一个联邦全部岛屿的各一张邮票时，可以上交这些邮票，得到这个联邦中全部岛屿对应的赏金。注意，每个联邦的赏金可以获得多次。

见钱眼开，你立马申请参加这次探索行动，行动投资方给了你一个初始电量为 c 的传送手环。每次移动，如果电量充足，你可以消耗 t_{i} 的电量，从任何地方传送到岛屿 i。

问，通过传送手环，你最多能获得多少赏金。

输入格式Input

第一行包括三个整数 n,m,c​（3≤n≤10^{3},0≤m≤2*10^{3},1≤c≤10^{5}​），表示岛屿数、桥数和手环初始电量。

第二行包括 n 个整数 a_{i}（1≤a_{i}≤10^{9}），表示每个岛屿对应的赏金。

第三行包括 n​ 个整数 t_{i}​（1≤t_{i}≤10^{3}​），表示传送到每个岛屿消耗的电量。

最后 m 行，每行输入一对整数 u 和 v（1≤u,v≤n），表示有一座桥连通岛屿 u 和岛屿 v。

输出格式Output

一个整数，表示你能获得的最多赏金数。

样例Sample

出题Author

Owaiter

来源Source