Fewest cancellations under capacity: hints, no solution

A clinic has a limited number of waiting-room chairs, given as chairs. Every appointment holds one chair for the whole of its [start, end) interval, in minutes, and an appointment that starts exactly when another ends can reuse that chair. Some appointments overlap, so at some minutes more chairs would be needed than the clinic owns.

Cancel as few appointments as possible so that at no minute do the remaining appointments need more than chairs chairs, and return how many were cancelled. Appointments are given in no particular order, may repeat, and each repeat is a separate appointment. Aim for O(n log n); an approach that tries subsets or re-checks every minute after each removal will be too slow.

Examples

Input

appointments = [[1, 4], [2, 5], [3, 6], [4, 7]], chairs = 2

Output

1

Note

At minute 3 three appointments run with two chairs; cancelling the one ending at 6 fixes every later minute too.

Input

appointments = [[1, 3], [3, 5], [5, 7]], chairs = 1

Output

0

Note

The appointments only touch, so a single chair is enough for all of them.

Input

appointments = [[0, 10], [0, 10], [0, 10], [0, 10], [0, 10]], chairs = 2

Output

3

Note

Five identical appointments with two chairs means three must be cancelled.

Constraints

• 0 <= appointments.length <= 20000 and 1 <= chairs <= 20000
• 0 <= start < end <= 1000000 for every appointment
• Repeated appointments are separate and each needs its own chair

Hint 1: a nudge

Sweep through time and look at the moment you first need more chairs than you have. Among the appointments running at that moment, which single one would be least costly to give up?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing