题目描述

从 $N$ 个夜市中选择其中几个夜市进行游玩，给定：

$A_i$：在夜市 $i$ 玩的乐趣值；

$B_i$：在夜市 $i$ 游玩的时长。

要求：

• 必须按顺序游玩；

• 在夜市游玩的时间是 $0$~$T$；

• 游玩时间不得与时间点 $S$ 重叠；

• 使游玩乐趣值之和 $M$ 尽可能大。

输入格式

第一行三个整数 $N$，$T$，$S$；

以下 $N$ 行，每行两个整数 $A_i$，$B_i$。

输出格式

一个整数 $M$。

样例

样例输入

5 20 14
8 9
2 4
7 13
6 3
5 8

样例输出

16

说明/提示

样例解释

$0$ 时游玩夜市 $1$；

$9$ 时游玩夜市 $2$；

$14$ 时游玩夜市 $4$；

$M=8+2+6=16$

数据范围

$10 \%$ 的数据满足：$N \le 20$

$20 \%$ 的数据满足：$S = 0$

全部的数据满足：

$1 \le N, T, B_i \le 3000$

$0 \le S \le T$

$0 \le A_i \le 10^5$

保证输入数据能够制定至少一种游玩方案。

Source

JOI 2011/2012 本選 問題3

Translate

By zerc