← 返回题目列表

AtCoder · pakencamp_2021_day2_g

G. 进击的巨人

中文机器翻译题面 查看原题

配点 : 400 点

問題文

PA实验室的负责人企鹅君想要增加PA实验室的房间数量。

企鹅君所在的学校 有 N 个房间和 1 房间来自 考虑一条使前往 N 。

另外,M 走廊里摆满了书籍。i 第二个走廊是一个房间 U_i 和房间 V_i 双向连接。您可以通过这些走廊从任何房间到达任何房间。

目前,Paken的俱乐部房间是一个房间 仅 1 。今天是企鹅 1 当天, 通过执行以下操作 1 日 1 次,N-1 当天,所有房间将被指定为 PA 实验室房间。

  • 通过走廊直接连接到当前为 PA 实验室俱乐部房间但当前不是 PA 实验室俱乐部房间的房间之一的房间。 1 选择一个房间并将其设为 Paken 的新俱乐部房间。

i 当天房间 当 j 被改造成一个新的学校俱乐部房间时,企鹅的幸福是 您也可以写 A_{i,j} 上升。起初,企鹅的幸福是 0 。

N-1 找出并输出一天操作结束时企鹅幸福感的最大可能值。

制約

  • 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\ (2 \leq j \leq N),\ A_{i,j} = 0\ (j = 1)
  • 从任何房间到任何房间 0 可以通过多个走廊
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N M
U_1 V_1
\vdots
U_M V_M
A_{1,1} A_{1,2} \cdots A_{1,N}
\vdots
A_{N-1,1} A_{N-1,2} \cdots A_{N-1,N}

出力

答案 请打印除以 1 行输出。


入力例 1

3 3
1 2
1 3
2 3
0 2 3
0 4 3

出力例 1

7

1 当天房间 当 2 是俱乐部房间, 如果2 当天房间 当 3 是俱乐部房间,幸福就是 A_{1,2} + A_{2,3} = 5

1 当天房间 当 3 是俱乐部房间, 如果2 当天房间 当 2 是俱乐部房间,幸福就是 A_{1,3} + A_{2,2} = 7

,所以答案是 7 输出。


入力例 2

4 5
1 3
2 3
3 4
2 4
1 4
0 1 2 3
0 31 41 59
0 1 6 82

出力例 2

115

原案: primenumber_zz