Painting the Fence

Farmer John has devised a brilliant method to paint the long fence next to his barn (think of the fence as a one-dimensional number line). He attaches a paint brush to his favorite cow Bessie, then relaxes with a cold glass of water while Bessie walks back and forth across the fence, painting one coat over every segment she passes.

Bessie starts at position $0$ and performs a sequence of $N$ moves ($1 \le N \le 100{,}000$). For example, the move "10 L" means Bessie moves $10$ units to the left, and "15 R" means she moves $15$ units to the right. Every segment she walks over receives one coat of paint. During her walk Bessie moves at most $1{,}000{,}000{,}000$ units away from the origin.

Given all of Bessie's moves, find the total length (area) of the fence that is painted with at least $K$ coats.

• Line 1: Two space-separated integers $N$ and $K$.
• Lines 2 to $N+1$: Each line describes one of Bessie's moves (for example, "15 L"): a distance followed by a direction character, L (left) or R (right).

• Line 1: The total length of the fence painted with at least $K$ coats.

Suppose $N = 6$, $K = 2$, and Bessie moves $2$ right, $6$ left, $1$ right, $8$ left, $1$ right, then $2$ right. The area painted with at least $2$ coats is $6$, consisting of the intervals [-11, -8], [-4, -3], and [0, 2].