Banner Home Page DIY Contests Problems Ranklist Status Statistics

涛涛的Party

Time Limit : 3000/1000ms (Java/Other)   Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 31   Accepted Submission(s) : 16

Font: Times New Roman | Verdana | Georgia

Font Size:

Problem Description

涛神因为极强,并且特别帅,所以拥有很多美女的联系方式,每个美女都有自己的食量以及魅力值,大家都知道,物以类聚,人以群分,朋友的朋友就是自己的朋友,所以美女一般都是有自己的美女朋友圈,而且这些美女特别团结,如果她的朋友有没有被邀请的她就不会答应邀请。涛涛想办一个party,但是他只准备了w kg的食物,他想获得最大的美女魅力值,不知道怎么邀请美女,于是他去问你,你能告诉他,他能获得的美女魅力数是多少吗

Input

数据有多组,第一行输入n,m和w(1≤n≤1000,0≤m≤min(n*(n-1)/2,10^5),1≤w≤1000);第二行输入n个整型变量w1,w2,...,wn(1≤wi≤1000)代表美女i的食量;第三行输入n个整型变量b1,b2,...,bn(1≤bi≤106)代表美女i的魅力值;接下来的m行输入两个数x和y(1≤xi,yi≤n,xi≠yi),代表x和y是朋友

Output

输出涛涛能获得的最大魅力值

Sample Input

3 1 5
3 2 5
2 4 2
1 2
4 2 11
2 4 6 6
6 4 2 1
1 2
2 3

Sample Output

6
1

Author

大豪哥

Source

jxnu

Statistic | Submit | Back