For convenience, we add a \(1\ 0\) operation to the beginning.

Assume a particular type-1 operation is the last one performed among type-1 operations. All operations before it will be irrelevant, and thus needn’t be skipped. All type-1 operations after it must be skipped. We needn’t skip any non-negative type-2 operations, so we pick the lowest negative type-2 operations to skip.

To implement this strategy, we consider the operations in reverse order.

We also consider a multiset or max-heap \(Q\), representing the type-2 ops we may want to skip, and a variable \(s := 0\), representing the sum of the type-2 ops we don’t skip.

The ops become:

\(2\ y\): If \(y \ge 0\), do \(s := s + y\). Otherwise, put \(y\) into \(Q\). If the size of \(Q\) exceeds \(K\), withdraw the maximum value from \(Q\) and add it to \(s\).

\(1\ y\): Update the answer: \(ans := \max(ans, y + s)\). If \(K = 0\), break early, otherwise decrement \(K\) (to account for skipping this op). This may cause the size of \(Q\) to exceed \(K\), if so, withdraw the maximum value from \(Q\) and add it to \(s\).

Time complexity: \(O(N \log K)\)