AT_pakencamp_2021_day2_g 進撃のパ研

ペンギン君想为パ研增加更多的部室。 在他的学校里有 $N$ 个房间，每个房间被编号为 $1$ 到 $N$。 另外，学校里有 $M$ 条走廊。第 $i$ 条走廊连接了房间 $U_i$ 和房间 $V_i$，这意味着通过这些走廊，任意两个房间之间都可以相互连通。 目前，パ研的部室仅位于房间 $1$。ペンギン君计划从今天开始，第 $1$ 天起，在接下来的 $N-1$ 天里每天最多进行一次操作，以确保到第 $N-1$ 天结束时所有房间都成为パ研的部室。 - 每次操作中，他可以从已经成为パ研部室的房间出发，通过一条直接相连的走廊拓展到尚未成为部室的房间，并把该房间设为新的パ研部室。 如果在第 $i$ 天选择房间 $j$ 成为新的パ研部室，则ペンギン君的"喜悦值"将增加 $A_{i,j}$, 初始状态下，喜悦值为 $0$。 请计算当第 $N-1$ 天完成所有操作后，ペンギン君可以获得的最大喜悦值。

输入以以下格式给出： > $N\ M\ U_1\ V_1\ \cdots\ U_M\ V_M\ A_{1,1}\ A_{1,2}\ \cdots\ A_{1,N}\ \cdots\ A_{N-1,1}\ A_{N-1,2}\ \cdots\ A_{N-1,N}$

输出一个整数，代表最大可能的喜悦值。

- $2 \leq N \leq 15$ - $1 \leq M \leq \frac{N(N-1)}{2}$ - $1 \leq U_i < V_i \leq N$ - 不存在两个相同的走廊，即 $(U_i,V_i) \neq (U_j,V_j)$ 对于$i \neq j$ - $1 \leq A_{i,j} \leq 10^5\ (\forall 2 \leq j \leq N)$ 且 $A_{i,1} = 0$ - 所有房间间都是连通的 - 输入的所有数值均为整数 ### 样例解释 在第 $1$ 天选择房间 $2$ 作为新部室，第 $2$ 天选择房间 $3$，则喜悦值为 $A_{1,2}\ +\ A_{2,3} = 5$。如果第 $1$ 天选择房间 $3$，第 $2$ 天再选择房间 $2$，则喜悦值为 $A_{1,3}\ +\ A_{2,2} = 7$。因此，应输出最大喜悦值 $7$。 **本翻译由 AI 自动生成**