1313: 20级算法课实验三：消消乐
Memory Limit：512 MB
Time Limit：3.000 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
小明最近迷上了消消乐这款游戏，这款游戏的规则如下：
游戏总共有 $n$ 个方块，你每次只能消除一个方块，消除规则如下：
1. 单独消除一个方块消耗 $x$ 的体力。
2. 如果你在消除完 $i$ 号方块再去消除 $j$号方块，则消耗 $ a_{ij}$ 的体力。
请问小明消除完所有方块最少需要消耗多少体力？
游戏总共有 $n$ 个方块，你每次只能消除一个方块，消除规则如下：
1. 单独消除一个方块消耗 $x$ 的体力。
2. 如果你在消除完 $i$ 号方块再去消除 $j$号方块，则消耗 $ a_{ij}$ 的体力。
请问小明消除完所有方块最少需要消耗多少体力？
Input
第一行两个整数 $n$ 和 $x$，分别表示方块的个数和单独消除一个方块消耗的体力。
接下来 $n$ 行，每行 $n$ 个数，第 $i$ 行第 $j$ 个数为 $a_{ij}$ 表示消除完 $i$ 号方块再消除 $j$ 号方块所消耗的体力。
(值得注意的是：题目保证 $a_{ij} = a_{ji} $，同时 $a_{ii}$ 的位置全为 $-1$,表示不存在此操作)
强调：$a_{ij}<=x$
接下来 $n$ 行，每行 $n$ 个数，第 $i$ 行第 $j$ 个数为 $a_{ij}$ 表示消除完 $i$ 号方块再消除 $j$ 号方块所消耗的体力。
(值得注意的是：题目保证 $a_{ij} = a_{ji} $，同时 $a_{ii}$ 的位置全为 $-1$,表示不存在此操作)
强调：$a_{ij}<=x$
Output
输出一行，表示小明消除 $n$ 个方块最小消耗的体力
Sample Input Copy
3 4
-1 2 3
2 -1 1
3 1 -1Sample Output Copy
7HINT
注意：请不要抄袭他人代码提交，所有的被OJ查重的代码即使正确也会被修改为答案错误
对于所有的样例 $1<=n<=5000, 1<=a_{ij}<=x<=100000$
请使用scanf进行输入
或者在main函数下加入如下代码
int main(){
std::ios::sync_with_stdio(false);
对于所有的样例 $1<=n<=5000, 1<=a_{ij}<=x<=100000$
请使用scanf进行输入
或者在main函数下加入如下代码
int main(){
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
//下面写你的代码
}
否则即使是正确的代码也可能时间超限
样例说明
第一步：消除1号方块，消耗4点体力
第二步：消除2号方块，因为1号方块已经消除，所以消耗 $a_{12}$ 点体力，即2点体力
第三步：消除3号方块，因为1号和2号方块都已经消除，所以可能消耗 $a_{13}$ 或 $a_{23}$ 点体力，取较小值，消耗1点体力
总共消耗7点体力