C - Reward for Carrying Luggage Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

N 個の部屋が一列に並んでおり、左から順に部屋 1, 部屋 2, \ldots, 部屋 N と番号が付けられています。高橋君はこれらの部屋を部屋 1 から部屋 N まで順に 1 つずつ訪れ、それぞれの部屋で提示される仕事を「引き受ける」か「断る」かを選びます。各部屋にはちょうど 1 つの仕事があり、各部屋を訪れるのは 1 回だけです。

各部屋 i の仕事には種類 T_i と報酬 A_i が設定されています。仕事の種類は次の 2 種類です。

  • 荷物を積む仕事 (T_i = 1)：引き受けると報酬 A_i を受け取り、荷物を 1 つ受け取る。持っている荷物の個数が 1 増える。
  • 荷物を降ろす仕事 (T_i = 0)：引き受けると報酬 A_i を受け取る。荷物を 1 つ以上持っている場合は荷物を 1 つ降ろし、持っている荷物の個数が 1 減る。荷物を 1 つも持っていない場合は、降ろす荷物がないため、荷物の個数は 0 のまま変わらない（報酬は受け取れる）。

高橋君の持っている荷物の個数は最初 0 です。仕事を引き受ける・断るを繰り返す過程を通じて、どの時点においても荷物の個数が K を超えてはなりません。荷物が多すぎると持ちきれなくなってしまうためです。

また、すべての部屋を訪れ終わった時点で荷物の個数がちょうど 0 でなければなりません（荷物を持ったままでは帰れないためです）。

これらの条件を満たすように高橋君が引き受ける仕事を選んだとき、引き受けた仕事の報酬の合計の最大値を求めてください。なお、1 つも仕事を引き受けないことも可能であり、その場合の報酬の合計は 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
  • 1 行目には、部屋の数 N と荷物の個数の上限 K が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各部屋の仕事の情報が与えられる。
  • 1 + i 行目には、部屋 i の仕事の種類 T_i (1 : 荷物を積む、0 : 荷物を降ろす) と報酬 A_i が、スペース区切りで与えられる。

出力

条件を満たすように引き受ける仕事を選んだとき、引き受けた仕事の報酬の合計の最大値を 1 行で出力せよ。

入力例 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

Score : 366 pts

Problem Statement

There are N rooms arranged in a row, numbered Room 1, Room 2, \ldots, Room N from left to right. Takahashi visits these rooms one by one in order from Room 1 to Room N, and for each room, he chooses to either "accept" or "decline" the job offered there. Each room has exactly one job, and he visits each room exactly once.

Each room i has a job with type T_i and reward A_i. There are two types of jobs:

  • Loading job (T_i = 1): If accepted, he receives reward A_i and picks up one piece of luggage. The number of pieces of luggage he is carrying increases by 1.
  • Unloading job (T_i = 0): If accepted, he receives reward A_i. If he is carrying one or more pieces of luggage, he puts down one piece, and the number of pieces of luggage he is carrying decreases by 1. If he is carrying no luggage, there is nothing to put down, so the number of pieces of luggage remains 0 (he still receives the reward).

The number of pieces of luggage Takahashi is carrying is initially 0. Throughout the process of accepting and declining jobs, the number of pieces of luggage must not exceed K at any point. This is because carrying too much luggage would be unmanageable.

Additionally, the number of pieces of luggage must be exactly 0 after visiting all rooms (because he cannot go home while still carrying luggage).

Determine the maximum total reward of the jobs Takahashi accepts while satisfying these conditions. Note that it is possible to accept no jobs at all, in which case the total reward is 0.

Constraints

  • 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
  • All input values are integers.

Input

N K
T_1 A_1
T_2 A_2
\vdots
T_N A_N
  • The first line contains the number of rooms N and the upper limit on the number of pieces of luggage K, separated by a space.
  • From the 2nd line to the (N + 1)-th line, the job information for each room is given.
  • The (1 + i)-th line contains the type T_i of the job in room i (1: loading, 0: unloading) and the reward A_i, separated by a space.

Output

Print in one line the maximum total reward of accepted jobs when choosing which jobs to accept while satisfying the conditions.

Sample Input 1

4 1
1 5
0 4
1 3
0 10

Sample Output 1

22

Sample Input 2

3 2
1 5
1 6
1 7

Sample Output 2

0

Sample Input 3

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

Sample Output 3

61

Sample Input 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

Sample Output 4

164

Sample Input 5

1 1
0 1000000

Sample Output 5

1000000