编程高手
测试数据来自 system/3009
作业已超过截止时间,您无法递交本题目。
时间限制:1秒 内存限制:256M
【问题描述】
老师给小H布置了 \(n\) 道编程题,可是他一道也不会……。
但他知道有 \(m\) 位高手,每位高手都能秒杀每道题目,但高手做题需要好处费。
小H打算聘请一些高手来帮助他完成所有题目,已知每位高手做每道题需要的好处费,并打算只允许每位高手最多做两道题。
请问小H至少要付出多少费用?
【输入格式】
第一行两个整数 \(n,m\) 表示有 \(n\) 道编程题和 \(m\) 位高手。
接下来是一个 \(m\) 行 \(n\) 列的整数矩阵(每个整数在 \(1..10000\) 范围内),矩阵中的第 \(i\) 行第 \(j\) 列的整数表示选手 \(i\) 完成题目 \(j\) 的好处费。
【输出格式】
一个整数,表示小H的最少花费。
【输入输出样例】
Input
4 3
2 5 3 1
5 2 6 2
4 1 5 3
Output
8
【样例解释】
一种花费最少的高手做题方案是:
第1个高手做第1题和第3题,花费为:2+3=5。
第2个高手做第4题,花费为:2。
第3个高手做第2题,花费为:1。
所以,总花费为:5+2+1=8.
【数据限制】
对于 \(40\%\) 的数据,保证\(3≤n,m≤10\)
对于 \(100\%\) 的数据,保证\(3≤n,m≤20\)