3652: 艰难睡眠(第六轮02)
题目描述
牛牛最近睡眠很艰难。
牛牛的宿舍楼有 n 个会吵闹的人，每个人都按照固定的吵闹时间吵闹，吵闹以外 的时间不会影响到牛牛睡眠。
每天有 m 分钟，从 1 到 m 标号。第 i 个人从第a_i分钟开始吵闹，吵闹时长为b_i 分钟，即在[a_i, a_i + b_i − 1]这段时间里保持吵闹。当然，可能会吵到第二天。 牛牛是个不能忍受吵闹的人，他决定花费一定的代价解决每一个人。
如果希望第 i 个人从第 j 分钟开始吵闹， 牛牛需要花费代价c_{i,j} 。显然， c_{i, a_i} = 0。
牛牛每天至少需要睡眠 k 分钟，牛牛是那种睡下去，就一定要睡足 k 分钟的人， 牛牛想知道自己花费的最小代价是多少。
当然，牛牛可以从一天的晚上睡到第二天的早上，但是得保证以后的每一天按同 样的方式睡眠都不会被吵到。
如果想得到最后 20 分，可能需要足够快的快速读入，这里提供一个 fread 的范 本：
namespace io {
const int L = (1 << 21) + 1;
char ibuf[L], *iS, *iT, obuf[L], *oS = obuf, *oT = obuf + L - 1, c, st[55]; intf, tp;
#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,L,stdin),(iS==iT?EOF:*iS++)):*iS++) inline void gi(int& x) { //get
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
}; // namespace io using io::gi;
使用方法 gi(n); 读入整数 n
注意， fread 需要从文件读入，不影响判题但是可能影响测试。
输入
第一行输入三个整数 n,m,k，表示吵闹的人的数目， 一天有几分钟和牛牛至少需 要的睡眠时间。
随后 n 行，第 i 行两个整数ai, bi， 即第 i 个人的开始吵闹时间和吵闹时长。
随后 n 行，每行 m 个整数，其中第 i 行第 j 个表示牛牛让第 i 个人从每天的第 j 分钟开始吵闹需要花费的代价ci,j 。
对于20%的数据有n ≤ 10, m ≤ 10。
对于40%的数据有n ≤ 100, m ≤ 100。
对于80%的数据有n ≤ 1000, m ≤ 1440。
对于100%的数据有2 ≤ n ≤ 5000, 1 ≤ ai, bi, k ≤ m ≤ 2000, 0 ≤ ci,j ≤ 104 。
输出
一行一个整数表示答案。
如果无论如何，牛牛都无法睡足 k 分钟，输出-1。
样例输入 复制
3 6 3
1 1
3 2
4 3
0 1 2 7 1 2
1 2 0 3 4 5
7 9 5 0 4 6
样例输出 复制
4提示
让 1 去时间 5 吵闹，吵闹时段为[5,5]。
让 2 去时间 4 吵闹，吵闹时段为[4,5]。
不改变 3 的吵闹时间，吵闹时段为[4,6]。 此时，牛牛可以在[1,3]时段睡觉。