题目描述

有 $n$ 个人 $(1\le n\le1000)$。每个人有一个重量 $w_i\ (1\le w_i\le 1000)$ 和一个魅力值 $b_i\ (1\le b_i\le 10^6)$。 $n$ 个人之间有 $m\ (1\le m\le\min(\frac{n\times(n-1)}{2}, 10^5))$ 个关系。第 $i$ 个关系由两个数字 $x_i$ 和 $y_i$ 组成，表示第 $x_i$ 个人和第 $y_i$ 个人是朋友，朋友关系是双向的。

已知若 $a$ 和 $b$ 是朋友，$b$ 和 $c$ 是朋友，则 $a$ 和 $c$ 是朋友。 现在 Mehrdad 要邀请一些人来到派对，使这些人的重量总和不超过 $w\ (1\le w\le1000)$，且魅力值总和尽量大。同一个朋友圈里的人，只能邀请其中的一个人，或者全部人，或者一个人也不邀请。

输入格式

第一行，三个整数 $n,m,w$。

第二行，$n$ 个整数 $w_1,w_2,\cdots,w_n$。

第三行，$n$ 个整数 $b_1,b_2,\cdots,b_n$。

接下来 $m$ 行，每行表示一个关系，第 $i$ 行有两个整数 $x_i$ 和 $y_i$。每一组朋友关系都是不同的。

输出格式

一行，表示最大的魅力值总和。

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