560. Non-Overlapping Intervals

0

Medium

Given an array of intervals, represented as [start_i, end_i], find the minimum number of intervals that need to be removed in order to make the remaining intervals non-overlapping.

Input Format

The first line contains the number of rows in the matrix.
The second line contains the number of columns in the matrix.
The third line contains the 2D matrix.

Output Format

Print the minimum number of intervals to be removed.

Example

Input

4
2
1 2
2 3
3 4
1 3

Output

1

Constraints

1 <= intervals.length <= 10^5
intervals[i].length == 2
-5 * 10^4 <= start_i, end_i <= 5 * 10^4

Loading...

View Submissions

Console