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