最大权值三角形对
题号:NC206127
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

    给一张阶无向图,有条边,无自环和平行边。每个点有一个权值,请找到两个三角形(长度为3的回路),使得它们至少有一个交点,且权值和最大(若某个点出现在两个三角形中,其权值只计算一次)。

输入描述:

第一行两个数
接下来一行个数,表示每个点的权值。
接下来行,每行两个数表示一条边。

输出描述:

一个数,表示最大权值和。
示例1

输入

复制
3 3
1 2 3
0 1
1 2
0 2

输出

复制
6

说明

选择两个三角形为(0,1,2)与(0,1,2)。
示例2

输入

复制
3 2
1 2 5
0 2
2 1

输出

复制
0

说明

无三角形。
示例3

输入

复制
6 11
7 8 6 8 9 7
0 1
0 2
0 3
0 4
0 5
1 3
2 4
2 5
3 4
3 5
4 5

输出

复制
39

说明

选择两个三角形为(3,0,1)与(3,4,5)。