A-唯物丁真遇上唯心王源：到了群星就要拿出真本事_2023河南萌新联赛第（八）场：南阳理工学院

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

在Stellaris的宇宙中，有着许多强大的帝国，帝国之间经常发生争斗，现在在宇宙中一共有 $w$ 个帝国。

有 $n$ 个星系，每个星系都被一个帝国所占领，有

条通道，每条通道可以让两个星系之间连通，但是通道仅有在两个星系都属于同一个帝国的时候，才可以发挥资源运输的作用。

由于丁真帝国和王源帝国的种族思想不同，丁真帝国想要发动星际战争攻打王源帝国，急需矿产资源，建造星际舰队，但是丁真帝国所占领的星系并没有互相连接，导致星系之间的矿产资源不能进行运输，所以只能在一块连通的地区内进行舰队的建造。不过丁真帝国已经可以建筑星门这种巨构，一个星门可以通往其他任意另一个星门，但是由于资源问题，丁真帝国最多只能建造 $k$ 个星门。

作为丁真帝国的总指挥的你现在需要计算怎么样建造星门才能使流通的矿产资源最大化（默认 1 属于丁真帝国）？

你说得对但是《王源剩太多》是由丁真珍珠自主研发的一款全新开放世界冒险游戏。游戏发生在一个被称作「理塘」的幻想世界，在这里被神选中的人将被授予「电子烟」，引导尼古丁之力。你将扮演一位名为「芙蓉王」的神秘角色，在自由的旅行中邂逅性格各异、能力独特的动物朋友们，和它们一起击败强敌，找回不存在的亲人的同时，逐步发掘「理塘」的真相。

输入描述:

第一行输入四个整数 $n$ ， $m$ ， $k$ ， $w$ ， $n$ 表示星系的数量， $m$ 表示通道的数量， $k$ 表示最多可以建造的星门的数量， $w$ 表示帝国的总数量 $1\leq n,w\leq 10^{6}$ ， $0\leq k,m \leq 10^6$ 。

第二行输入一行正整数 $a_i$ ，表示第 $i$ 个星系的矿产资源总数， $0\leq a_i \leq 10^6$ 。

第三行输入一行正整数 $b_i$ ，表示第 $i$ 个星系的属于哪个帝国， $1\leq b_i \leq n$ ，默认 1 属于丁真帝国

接下来 m 行每行两个数 $x,y$ ，表示星系 $x$ 与星系 $y$ 之间有一条通道连接， $1\leq x,y \leq n$ ，数据保证不会有重边和自环。

输出描述:

输出一个整数，表示丁真帝国最大的流通矿物资源数量。

示例1

输入

复制

7 6 3 3
5 8 9 4 5 4 5
1 2 3 1 1 1 1
1 2
2 3
2 4
4 5
3 6
3 7

输出

复制

备注:

样例中，4和5是相互连接的，用星门将1,4,5,7连通，最大的矿产流通资源量为19