Given any solution, we can decide to first do all tab additions and then all deletions, since the order of operations is irrelevant. Using this convention, we can ignore the rule stating that no line should have less than zero tabs during algorithm execution.

The task can be interpreted as follows: we will define a sequence of numbers in which the ~i^\text{th}~ number equals ~K_i-P_i~. We will also define two queries: increment or decrement (by one) all numbers from a particular range. Those ranges will be referred to as positive and negative ranges, respectively. The goal is then to transform the initial sequence to a sequence of all zeros by executing a minimal number of queries.

Solution

Let us consider an optimal solution which consists of some number of positive and negative ranges. We choose a positive and a negative one which overlap, if such exist.

There are four distinct cases of overlapping ranges:

1. Both ranges are equal. This means that the solution found is not optimal, since the two queries will cancel out.
2. Both ranges have equal upper or lower bound. This also means that the solution found is not optimal, since the same effect can be achieved by a single positive or negative range equal to their difference.
3. The ranges share no equal bounds but one range is contained within another. We observe that the overlapping part of the ranges cancels out, but since two ranges are necessary in either case, both solutions are equally good.
4. The ranges share no equal bounds but they partially overlap. The overlapping part again cancels out, and the effect is the same as if we had two non-overlapping ranges. The number of ranges (two) remains unchanged, making both solutions equally good.

Therefore, whenever we encounter cases 1 or 2, we can replace two ranges with a single one, as described above. By applying consecutive replacements for those two cases, it is obvious that the number of ranges is decreasing. Therefore, at some point, we will reach the minimum number of ranges, which means an optimal solution is found. By also substituting ranges in cases 3 and 4, we can always obtain an optimal solution in which no two ranges overlap.

We can divide the sequence into contiguous subsequences of only nonnegative or only nonpositive numbers. This alternating division can be found with linear complexity. Each of them can be solved separately using only negative or only positive intervals, respectively. Since the cases are mutually analogous, in the remainder of the discussion we will consider solving the case with nonnegative numbers using negative intervals.

If there is a zero value in the subsequence, we can divide it into the part left of that zero and the part right of it and solve each of these parts separately. It can always be done since there will never be an interval overlapping a zero in the optimal solution. If there is no zero value, we can use a single interval to solve the subsequence and repeat the same procedure (which has possibly created some zeros). This process will eventually result in an optimal solution. Proving this fact is not difficult, so it is left as an exercise for the reader.

We can represent the (nonnegative) subsequence as a histogram, where numbers represent column heights. One possible way of obtaining a solution for a (sub)sequence is using recursion. We can find the smallest number ~B~ using an interval tree. After that, we use a negative interval on the subsequence ~B~ times, zeroing the smallest number. Then we can divide the subsequence around the newly created zero and solve the left and right parts recursively. The complexity of this algorithm is ~\mathcal O(N \log N)~.

This recursive algorithm actually divides the histogram into a binary tree, branching to two smaller disjoint cases in each step. Instead of recursion, we can use a well-known algorithm with complexity ~\mathcal O(N)~ using a stack.

Alternative solution

There is a completely different solution, using dynamic programming, that does not depend on the facts proven above. The state is determined by three numbers:

1. the number of opened positive intervals
2. the number of opened negative intervals
3. the index of the current position

In each step, we can:

1. open a new interval beginning at the current index
2. close a previously opened interval (ending it with the previous index)
3. if the number of positive and negative intervals matches the required number of tabs, we can move on to the next index

This algorithm can be implemented with complexity ~\mathcal O(NM^2)~, where ~M~ is the largest number of tabs that can appear in a row.