分数: 400 分
问题陈述
高桥接到的任务是在展厅的长廊上放置广告牌。走廊被分成若干个槽位 1 米,总长度为 L 米。也就是插槽 1, 2, \ldots, L 排成一排。
高桥有 N 广告板作为候选。全部 N 广告牌各不相同,他可以独立选择是否安装每一个广告牌。每个面板最多可以安装一次,如果安装了,可以随意放置在走廊沿线的任何位置(只要满足下述约束条件)。没有基于放置顺序或面板编号的限制。
的 i第一个广告面板(1 \leq i \leq N) 占用 w_i 连续时隙。具体来说,如果 i第一个广告面板安装时其左边缘与插槽对齐 s,占用槽位 s, s+1, \ldots, s+w_i-1 (其中 1 \leq s 和 s + w_i - 1 \leq L 必须保持)。如果 i安装了第一个广告面板,它提供了以下的吸引效果 b_i。未安装的面板不会产生吸引效果。
广告面板不能相互重叠。也就是说,两个不同安装的广告面板不能同时占据同一个槽位。只要它们不重叠,将它们彼此相邻放置也是可以接受的。
一旦选定的广告面板的位置确定,任何未被任何广告面板占用的槽位将成为 空位。如果没有安装面板,则所有槽位均为空槽位。
该走廊有消防安全规定。走廊墙壁上每隔一段距离就安装有紧急引导灯,在空位较长的区域,人们担心游客可能不会注意到引导灯。因此,以下 消防安全规定 必须满足:
不得有 走廊上有 K 或多个连续的空位。也就是说,连续空闲时隙的任何最大间隔的长度必须是 每个地点的 K-1 或更少。
此限制也适用于走廊两端附近。例如,如果最左边安装的广告面板的左边缘位于槽位 s,然后插槽 1 通过 s-1 均为空槽,形成 s-1 连续的空位,所以 s - 1 \leq K - 1 必须保留。同样,如果最右边安装的广告面板的右边缘位于槽位 t,然后 L-t 槽位中连续的空槽位 t+1 到插槽 L 还必须满足 L - t \leq K - 1.
如果没有安装广告牌,所有 L 插槽中的插槽 1 到插槽 L 是连续的空槽。因此,只有在以下情况下,未安装面板的位置才满足消防安全规定: L \leq K - 1 (即 L < K)。在这种情况下,总的吸引效应为 0.
高桥希望在满足消防安全规定的同时,最大限度地提高已安装广告牌的总体吸引力效果。
如果存在至少一种满足消防安全规定的广告牌的选择和放置方式,则输出最大的总吸引效果。如果不存在满足消防安全规定的场所,则输出 -1.
约束
- 1 \leq N \leq 400
- 1 \leq L \leq 1000
- 1 \leq K \leq L
- 1 \leq w_i \leq L (1 \leq i \leq N)
- 1 \leq b_i \leq 10^6 (1 \leq i \leq N)
- 所有输入值均为整数。
输入
N L K w_1 b_1 w_2 b_2 \vdots w_N b_N
- 第一行包含候选广告面板的数量 N,走廊的总长度 L,以及值 K 涉及连续空位的数量上限,以空格分隔。
- 从第 2 行到 (N + 1)第行,给出了每个广告面板的信息。的 (1 + i)- 第行 (1 \leq i \leq N) 包含槽数 w_i 占用 i第一个广告牌及其吸引效果 b_i,用空格分隔。
输出
如果存在满足消防安全规定的放置,则输出一行中最大的总吸引效果。如果不存在这样的位置,则输出 -1 一行。
示例输入 1
4 8 3 2 5 3 8 1 2 4 7
示例输出 1
17
示例输入 2
3 5 1 2 10 4 20 4 30
示例输出 2
-1
示例输入 3
12 30 5 3 12 7 25 4 14 6 18 2 7 5 16 8 30 1 3 9 28 4 13 10 35 6 20
示例输出 3
109
示例输入 4
30 100 7 5 120 12 260 7 150 20 500 3 60 15 330 8 180 10 210 6 140 25 620 4 90 18 410 9 200 11 240 13 290 2 45 16 370 14 310 7 170 5 115 22 540 19 430 1 20 30 750 6 135 10 230 17 390 8 175 24 580 12 255
示例输出 4
2475
示例输入 5
1 1 1 1 100
示例输出 5
100