Painted Fence

Farmer John has devised an ingenious method to paint his barn fence. He attaches a paintbrush to his favorite cow Bessie and lets her wander along the fence (which can be considered as a one-dimensional number line). Bessie starts from position 0 and makes N moves. Each move is given in the format distance direction (for example, 10 L indicates she moves 10 units to the left, and 15 R indicates she moves 15 units to the right). Every time Bessie traverses a segment of the fence, that segment is painted once. Note that the same segment can be painted multiple times if Bessie walks over it repeatedly.

Farmer John is interested in finding the total length of the fence that receives at least \(K\) coats of paint. Formally, if a section of the fence is painted \(C\) times, it is counted if \(C \ge K\). Given that Bessie can move up to 1,000,000,000 units away from the origin, you may need to use coordinate compression or an efficient sweep-line technique.

Input Constraints:

• \(1 \le N \le 100,000\)
• Each move is in the format: distance direction, where direction is either L (left) or R (right).
• Bessie starts at position 0.

Hint: Using a sweep-line algorithm with event counting is an efficient way to solve this problem. The changes of paint coats at endpoints can be recorded as events, and then sorted by coordinate. The total length where the accumulated coats is at least \(K\) can be computed by summing the differences between successive unique coordinates that meet the criteria.

inputFormat

The first line of input contains two space-separated integers: N and K. \(N\) is the number of moves and \(K\) is the minimum number of coats of paint required for a segment to be counted.

Each of the next \(N\) lines contains a move described by an integer and a character (either L or R), separated by a space.

outputFormat

Output a single integer representing the total length of the fence that has been painted with at least \(K\) coats.

sample

3 2
2 R
3 L
1 R

3