D 冒险者的奖励之路 (adventure)

题目描述

在一个神秘的大陆上，有 $n$ 个重要的探险地点，每个地点都有其独特的挑战和宝藏。每个地点的编号从 $1$ 到 $n$，并且这些地点的高度是按顺序从低到高排列的。为了帮助冒险者更方便地穿越这片大陆，人们修建了 $m$ 条连接不同地点的传送门，每个传送门只能将冒险者从一个较低的地点传送到一个较高的地点。

每个地点都有一个神秘的商店，商店的背后有不同的冒险公会经营。第 $i$ 个地点的商店属于第 $c_i$ 号公会，并且两个地点 $i$ 和 $j$ 如果属于同一个公会，则它们的商店背后有相同的奖励。每个公会都提供一个新成员专享的奖励红包，第 $i$ 个公会的红包金额为 $w_i$ 元。每个冒险者在接受过同一公会的奖励后，无法再从该公会的其他商店领取奖励。

你作为一名勇敢的冒险者，从 $1$ 号地点出发，准备依靠传送门到达各个地点。每当到达一个地点时，你都可以领取该地点商店提供的公会奖励红包（即便是 $1$ 号地点也有奖励）。但是同一家公会的红包只能领取一次。请你为每个可能的目的地 $k$，找到一条最佳的路径，使得你在到达 $k$ 号地点时，能够获得的奖励红包总额最大。

输入格式

第一行包含两个正整数 $n, m$ ($2 \leq n \leq 36$, $1 \leq m \leq \frac{n(n-1)}{2}$)，分别表示探险地点的数量和传送门的数量。

第二行包含 $n$ 个正整数 $c_1, c_2, \dots, c_n$ ($1 \leq c_i \leq n$)，依次表示每个地点的商店所隶属的公会编号。

第三行包含 $n$ 个正整数 $w_1, w_2, \dots, w_n$ ($1 \leq w_i \leq 10^6$)，依次表示每个公会的奖励红包金额。

接下来 $m$ 行，每行包含两个正整数 $u_i, v_i$ ($1 \leq u_i < v_i \leq n$)，表示一条传送门路线，起点是地点 $u_i$，终点是地点 $v_i$。输入保证任意两个地点之间最多只有一条传送门路线，且从 $1$ 号地点出发可以到达任意一个地点。

输出格式

输出 $n$ 行，第 $i$ 行输出一个整数，即从 $1$ 号地点出发到达 $i$ 号地点时，能够领取的奖励红包的最大金额。

样例

样例输入 1

5 8
3 4 3 3 3
2 5 7 7 8
1 2
1 3
1 4
2 3
2 4
3 4
3 5
4 5

样例输出 1

7
14
14
14
14

样例输入 2

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

样例输出 2

7
13
7
14
18
19
8
14

数据范围与约定

对于 $100\%$ 的数据，满足：

• $n, m$ ($2 \leq n \leq 36$, $1 \leq m \leq \frac{n(n-1)}{2}$)
• $1 \leq c_i \leq n$
• $1 \leq w_i \leq 10^6$
• $1 \leq u_i < v_i \leq n$