5650. 星星点灯
时间限制：1000 MS 内存限制：256 MB
题目描述
# 题目描述 A 市迎来了当地的传统节日——一年一度的观星节。 主办方请来了著名绘画大师大 D 画下了当晚天上的 $n$ 颗星星，参与者可以花费 $m$ 点星光能量为任意一颗星星点一盏灯。 除此之外，主办方还制作了一个 $n \times n$ 的表格，表格中第 $i$ 行第 $j$ 列的数字 $F\_{i,j}$ 表示如果目前第 $i$ 颗星星是亮的，那么可以花费 $F\_{i,j}$ 点星光能量为第 $j$ 颗星星点亮一盏灯。特别地，对于任何 $a, b$，$F\_{a,b}$ 总是等于 $F\_{b,a}$。 大 D 看着这些灯，心里盘算着最少花费多少星光能量能够为所有的星星点一盏灯。 # 输入格式 第一行两个整数 $m, n$，含义如题所示。 接下来 $n$ 行，每行 $n$ 个整数，第 $i$ 行第 $j$ 个整数表示 $F\_{i,j}$。 # 输出格式 一行一个整数，输出点亮所有灯所需最少的星光能量。 # 输入输出样例 ## 输入样例 #1 ``` 5 3 3 2 3 2 4 1 3 1 4 ``` ## 输出样例 #1 ``` 8 ``` ## 样例 #1 解释 在样例 1 中，先支付 $5$ 点星光能量点亮第二颗星星的灯，然后通过 $F\_{2,1}$ 和 $F\_{2,3}$ 点亮第一颗和第三颗星星的灯。总共花费了 $m + F\_{2,1} + F\_{2,3} = 5 + 2 + 1 = 8$ 点星光能量。 ## 输入样例 #2 ``` 10 5 6 2 3 5 2 2 4 1 5 7 3 1 3 4 3 5 5 4 3 6 2 7 3 6 4 ``` ## 输出样例 #2 ``` 19 ``` # 说明/提示 对于 $100\%$ 的数据，$1 \le m, F\_{a,b} \le 1000$。 | 测试点编号 | $n$ | | :---: | :---: | | $1 \sim 2$ | $\le 4$ | | $3 \sim 6$ | $\le 100$ | | $7 \sim 10$ | $\le 1000$ |