BZPRO
#4883. [Lydsy1705月赛]棋盘上的守卫
内存限制：256 MiB
时间限制：3 Sec
提交
提交记录
讨论
题目描述
在一个n*m的棋盘上要放置若干个守卫。对于n行来说，每行必须恰好放置一个横向守卫；同理对于m列来说，每列
必须恰好放置一个纵向守卫。每个位置放置守卫的代价是不一样的，且每个位置最多只能放置一个守卫，一个守卫
不能同时兼顾行列的防御。请计算控制整个棋盘的最小代价。
输入格式
第一行包含两个正整数n,m(2<=n,m<=100000,n*m<=100000)，分别表示棋盘的行数与列数。
接下来n行，每行m个正整数
其中第i行第j列的数w[i][j](1<=w[i][j]<=10^9)表示在第i行第j列放置守卫的代价。
输出格式
输出一行一个整数，即占领棋盘的最小代价。
样例
样例输入
3 4
1 3 10 8
2 1 9 2
6 7 4 6
样例输出
19
HINT
在(1,1),(2,2),(3,1)放置横向守卫，在(2,1),(1,2),(3,3),(2,4)放置纵向守卫。
数据范围与提示
BZPRO