厄神降临之路

题号：NC252370
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

键山雏有一个 $n$ 个点的简单无向图，点 $i$ 有点权 $a_i$ ，点 $i$ 与点 $j$ 之间的连边（如果存在）有边权 $e_{ij}$ 。定义一条路径的花费是该路径上的点权之和以及边权之和的乘积。
键山雏想要你帮忙找出花费最小的环。如果你找不着，厄运就到你身上啦！

环是从一个点出发，不经过一条边一次以上，再回到这个点的路径。

第一行一个正整数 。
接下来  个正整数，第  个整数代表点  的点权。
接下来  行，每行  个非负整数，第  行第  列的整数  代表点  与点  之间的边权。若 ，表示点  与点  之间的连边不存在。

一个正整数表示回路的最小花费，或输出  表示回路不存在。

示例1

复制

复制

-1

示例2

复制

5
10 10 10 4 1
0 0 2 5 0
0 0 6 5 7
2 6 0 1 0
5 5 1 0 0
0 7 0 0 0

复制