← 返回题目列表

AtCoder · awc0080_c

C. 携带行李奖励

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

分数: 366 分

问题陈述

有 N 房间排列成一排,编号为Room 1,房间 2, \ldots,房间 N 从左到右。高桥按照房间的顺序一一参观这些房间 1 到房间 N,对于每个房间,他选择“接受”或“拒绝”那里提供的工作。每个房间都有一份工作,他只访问每个房间一次。

每个房间 i 有一份类型为 T_i 和奖励 A_i。有两种类型的工作:

  • 正在加载作业 (T_i = 1): 如果被接受,他会收到奖励 A_i 并拿起一件行李。他携带的行李件数增加了 1.
  • 卸载作业 (T_i = 0): 如果被接受,他会收到奖励 A_i。如果他携带一件或多件行李,他放下一件,他携带的行李件数减少 1。如果他没有携带行李,则没有什么可放下的,因此行李件数仍为 0 (他仍然收到奖励)。

高桥携带的行李件数最初为 0。在接受和拒绝工作的整个过程中, 行李件数不得超过 K 在任何一点。这是因为携带太多行李会难以管理。

此外, 行李件数必须准确 0 参观完所有房间后 (因为他不能带着行李回家)。

确定高桥在满足这些条件的情况下接受的工作的最大总奖励。请注意,有可能根本不接受任何工作,在这种情况下,总奖励为 0.

约束

  • 1 \leq K \leq N \leq 10^5
  • N K \leq 10^7
  • T_i \in \{0, 1\}
  • 1 \leq A_i \leq 10^6
  • 所有输入值均为整数。

输入

N K
T_1 A_1
T_2 A_2
\vdots
T_N A_N
  • 第一行包含房间数 N 及行李件数上限 K,用空格分隔。
  • 从第 2 行到 (N + 1)第行,给出了每个房间的工作信息。
  • 的 (1 + i)第行包含类型 房间工作的 T_i 房间里的工作 i (1:加载, 0:卸载)和奖励 A_i,用空格分隔。

输出

在满足条件的情况下选择接受哪些工作时,一行打印所接受工作的最大总奖励。


示例输入 1

4 1
1 5
0 4
1 3
0 10

示例输出 1

22

示例输入 2

3 2
1 5
1 6
1 7

示例输出 2

0

示例输入 3

10 2
0 6
1 4
1 7
0 5
1 9
1 8
0 3
0 10
1 2
0 11

示例输出 3

61

示例输入 4

20 4
0 3
1 8
1 5
1 6
0 4
1 7
1 2
0 9
1 10
1 11
0 1
0 12
1 13
1 14
0 15
1 16
0 17
1 18
0 19
1 20

示例输出 4

164

示例输入 5

1 1
0 1000000

示例输出 5

1000000