Overview

This problem is solved using dynamic programming where the state is “how many packages you are currently carrying.”
By scanning the rooms from left to right and updating the maximum reward for each number of packages, we can find the maximum reward satisfying the conditions.

Analysis

At each room, you choose to “accept / decline” a job, but the only things relevant to the constraints are:

• How far you have looked so far
• How many packages you are currently carrying

These are the only two factors.

In other words, the detailed information about which jobs you selected in the past is unnecessary, and
it suffices to keep only “the current number of packages” as the state.

---

1. Naive exhaustive search is infeasible

Since there are 2 choices at each room, an exhaustive search would yield \(2^N\) possibilities.
With \(N \le 10^5\), this is obviously too slow.

---

2. Consider a state DP

Define the DP as follows:

• \(dp[j]\) := “Among all ways of choosing jobs from the rooms seen so far such that you are carrying \(j\) packages, the maximum reward obtainable”

In the initial state, you carry 0 packages, so:

• \(dp[0] = 0\)
• \(dp[j] = -\infty \ (j \ge 1)\)

What we ultimately need is “carrying 0 packages after processing all rooms,” so the answer is the final value of \(dp[0]\).

---

3. Consider the transitions

Loading job (\(T_i = 1\))

You earn reward \(A_i\), and the number of packages increases by 1.

• Decline: the number of packages stays the same
• Accept: \(j \to j+1\) (provided \(j+1 \le K\))

Therefore, the transitions are:

[ \text{newdp}[j] = \max(\text{newdp}[j], dp[j]) ] [ \text{newdp}[j+1] = \max(\text{newdp}[j+1], dp[j] + A_i) ]

---

Unloading job (\(T_i = 0\))

You earn reward \(A_i\), and:

• If you have 1 or more packages, the count decreases by 1
• If you have 0 packages, it stays at 0

That is, if you accept:

• If \(j \ge 1\), then \(j \to j-1\)
• If \(j = 0\), then \(0 \to 0\)

Therefore, in addition to:

[ \text{newdp}[j] = \max(\text{newdp}[j], dp[j]) \quad \text{(decline)} ]

• For \(j \ge 1\): \(dp[j] + A_i\) contributes to \(\text{newdp}[j-1]\)
• For \(j = 0\): \(dp[0] + A_i\) contributes to \(\text{newdp}[0]\)

---

4. “Unloading with 0 packages” is always beneficial

In this problem, \(A_i \ge 1\).
Therefore, accepting an “unloading job” when you have 0 packages does not change the number of packages and only increases the reward.

In other words, there is no reason to decline that job when you have 0 packages.

Thanks to this property, the transition for \(j=0\) during an unloading job can be written as:

[

\text{newdp}[0]

\max(dp[0] + A_i,\ dp[1] + A_i) ]

(The “decline” option gives \(dp[0]\), but since \(A_i > 0\), \(dp[0] + A_i\) is always better.)

---

5. Why a 1-dimensional DP suffices

Originally, including whether we have processed up to the \(i\)-th room as part of the state would make it a 2-dimensional DP. However, since updating each room only uses “the previous state,” the \(i\) dimension is unnecessary.

Therefore, it can be compressed into a 1-dimensional DP with a single array.

---

6. Naive in-place updates break correctness, so pay attention to update order

When updating in place with a 1-dimensional array, you need to be careful about the update order to avoid effectively using the same room’s job multiple times.

• Loading job: The transition goes \(j \to j+1\), so update from large \(j\) to small \(j\)
• Unloading job: The transition goes \(j+1 \to j\), so update from small \(j\) to large \(j\)

This ensures correct transitions where each room’s job is used at most once.

Algorithm

Use a DP array \(dp[0 \ldots K]\).

• Initialization:
  • \(dp[0] = 0\)
  • All others are \(-\infty\)

For each room \((T_i, A_i)\), do the following:

1. \(T_i = 1\) (Loading job)

The number of packages increases by 1, so update from the back.

[ dp[j+1] = \max(dp[j+1], dp[j] + A_i) \quad (j = K-1, K-2, \dots, 0) ]

For the “decline” case, simply leave \(dp[j]\) as is.

---

2. \(T_i = 0\) (Unloading job)

The number of packages decreases by 1 (stays at 0 if already 0), so update from the front.

First, since \(dp[0]\) can come from both the old \(dp[0]\) and \(dp[1]\), compute it beforehand:

[ best0 = \max(dp[0] + A_i,\ dp[1] + A_i) ]

Next, for \(j = 1\) to \(K-1\):

[ dp[j] = \max(dp[j], dp[j+1] + A_i) ]

Finally, set:

[ dp[0] = best0 ]

\(dp[K]\) can only remain from the “decline” case, so it stays as is.

---

After processing all rooms,

[ dp[0] ]

is the answer.

Complexity

• Time complexity: \(O(NK)\)
• Space complexity: \(O(K)\)

Since the constraints include \(NK \le 10^7\), this complexity is well within the time limit.

Implementation Notes

• Initialize unreachable states with a sufficiently small value (e.g., -10**30)
• Loading jobs: update from back to front
• Unloading jobs: update from front to back
• For unloading jobs, save the value for dp[0] into a separate variable best0 before overwriting dp[1]

By following these three points, you can safely implement the 1-dimensional DP in code.

Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    it = iter(data)
    N = next(it)
    K = next(it)

    NEG = -10**30
    dp = [NEG] * (K + 1)
    dp[0] = 0

    for _ in range(N):
        t = next(it)
        a = next(it)

        if t == 1:
            for j in range(K - 1, -1, -1):
                v = dp[j] + a
                if v > dp[j + 1]:
                    dp[j + 1] = v
        else:
            best0 = dp[0] + a
            v = dp[1] + a
            if v > best0:
                best0 = v
            for j in range(1, K):
                v = dp[j + 1] + a
                if v > dp[j]:
                    dp[j] = v
            dp[0] = best0

    print(dp[0])

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.