# 光棱坦克

- 参考时间限制：0.5 秒（参考环境：[评测环境与性能](../../../docs/评测环境与性能.md)；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：128 MB

## 背景故事

未来科技公司为光棱坦克装上了增强激光发射器和超时空链路，准备到尤里的前哨基地做一次实地演示。激光能够沿建筑间的路径折射，链路则可以提前阻断其中一些路径。

原型机造价不菲，又没有其他部队掩护。演示只有一次开火的机会，随后就得撤离。董事长已经准备好了宣传稿，现在只差一个经得起计算的“最大期望伤害”。

## 形式化问题描述

给定 $n$ 个顶点和 $e$ 条无向边组成的森林，顶点编号为 $1$ 到 $n$ . 顶点 $i$ 被击中时产生伤害 $d_i$ ，其折射概率为 $p_i$ .

攻击前，每个顶点可以选择至多 $b$ 条与它相连的边进行阻断。**一条边只要被任意一个端点选中，就会被阻断**；它仅占用主动选择该边的端点的名额。随后选择一个顶点作为初始攻击点。

每个顶点至多被击中一次。顶点 $i$ 被击中后，令 $C$ 为沿未被阻断的边与它相邻、且尚未被击中的顶点集合：

- 若 $C$ 为空，该顶点不再向其他顶点折射。
- 否则，以 $p_i$ 的概率击中 $C$ 中所有顶点；以 $1-p_i$ 的概率从 $C$ 中等概率选择一个顶点击中。
- 新击中的顶点继续按同样规则折射，各次随机选择相互独立。

总伤害为所有被击中顶点的 $d_i$ 之和。攻击点和全部阻断选择均在随机过程开始前确定。设最优策略的期望总伤害为 $V$ ，输入给定的取整偏移量为 $\delta$ ，输出 $\lfloor V+\delta+0.5\rfloor$ .

## 输入格式

第一行依次包含顶点数 $n$ 、每个顶点的阻断名额 $b$ 、边数 $e$ 和取整偏移量 $\delta$ . 前三项为整数，最后一项为实数。

接下来 $e$ 行，每行两个整数 $u,v$ ，表示一条边。

接下来一行包含 $n$ 个实数 $d_1,\ldots,d_n$ .

最后一行包含 $n$ 个实数 $p_1,\ldots,p_n$ .

## 输出格式

输出一个整数，即 $\lfloor V+\delta+0.5\rfloor$ .

## 样例 1

### 输入

```text
3 1 2 0.00
3 2
1 3
1.00 2.00 3.00
0.500 0.500 0.800
```

### 输出

```text
6
```

### 解释

不阻断路径并攻击顶点 $1$ ，三个顶点都会被击中，总伤害为 $6$ .

## 样例 2

### 输入

```text
6 0 5 0.50
2 3
4 6
4 3
1 2
2 5
1.00 2.00 3.00 4.00 5.00 6.00
0.500 0.500 0.500 0.500 0.500 0.500
```

### 输出

```text
20
```

### 解释

攻击顶点 $6$ 时依次击中 $6,4,3,2$ ，其伤害之和为 $15$ . 在顶点 $2$ 处，以相同概率击中剩余两个顶点，或等概率选择其中一个，因此这一步的期望伤害为 $0.5\times(1+5)+0.5\times(1+5)/2=4.5$ . 此时总期望 $19.5$ 为所有策略中的最大值；加入 $\delta=0.50$ 并取整，得到 $20$ .

## 样例 3

### 输入

```text
5 1 4 0.00
1 2
1 3
1 4
1 5
0.00 10.00 9.00 0.00 0.00
0.000 0.000 0.000 0.000 0.000
```

### 输出

```text
19
```

### 解释

让顶点 $4$ 选择阻断边 $(1,4)$ ，顶点 $5$ 选择阻断边 $(1,5)$ . 每个顶点都没有超过一个名额，顶点 $1$ 也不需要为这两条边消耗名额。

随后攻击顶点 $2$ ，激光依次击中 $2,1,3$ ，总伤害为 $19$ . 这已经等于所有顶点的伤害之和，因此最优。

## 数据范围与保证

- $1\le n\le2000$ ，$0\le e\le n-1$ ，$0\le b\le e$ .
- $1\le u,v\le n$ ；没有自环、重边或环，允许不连通。
- $0\le d_i\le5000$ ，$0\le p_i\le1$ ，$0\le\delta\le1$ .
- $d_i$ 和 $\delta$ 至多两位小数，$p_i$ 至多三位小数。
- 设 $z=V+\delta$ ，保证 $\lvert z-\lfloor z+0.5\rfloor\rvert\le0.3$ ，即结果远离取整分界。

### 数据分组

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |