← 返回题目列表

AtCoder · awc0099_d

D. 展厅广告投放

中文机器翻译题面 查看原题

分数: 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