408959: GYM103389 C 连锁商店

比特山是一个旅游胜地，它一共有 $$$n$$$ 个景点，按照海拔高度从低到高依次编号为 $$$1$$$ 到 $$$n$$$。为了更好地帮助游客们欣赏这里的风景，人们在上面搭建了 $$$m$$$ 条缆车路线。每条缆车路线只可能把游客们从某个海拔较低的景点运送到另一个海拔较高的景点。

在每个景点都有一家纪念品连锁商店，其中第 $$$i$$$ 个景点的商店隶属第 $$$c_i$$$ 号公司，两家连锁店 $$$(i,j)$$$ 隶属同一公司当且仅当 $$$c_i=c_j$$$。每家公司都有新客优惠活动，其中第$$$i$$$家公司对于新客的优惠红包为 $$$w_i$$$ 元，一旦领取了隶属该公司的某家连锁店的一份红包，就不能再领取该公司所有分店的红包。

你正在 $$$1$$$ 号景点，你将会搭乘缆车去往各个景点，每到一个景点，你都可以领取该景点的连锁商店的新客优惠红包（包括 $$$1$$$ 号景点）。当然，同一家公司的红包最多只能领一次。请写一个程序，对于每个可能的终点 $$$k$$$，找到一条从 $$$1$$$ 号景点出发到达 $$$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$$$ 号景点时，领取的优惠红包的总金额的最大值。

5 5
1 2 2 3 4
1 4 5 9 3
1 2
2 3
3 5
1 4
4 5

1
5
5
6
15