LCC '23 Contest 4 J2 - Watching Tutorials

View as PDF

Submit solution

Points: 3
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

With the CCC coming up soon, AngelsandDevsLOL realizes that she is a bit underprepared! She decides to watch some YouTube tutorials about different algorithms! She comes to the conclusion that the more tutorials she watches, the better her score will be in the CCC. To achieve a high score, she decides to watch multiple videos at the same time!

Her screen can be split into N rows and M columns of small windows. With some help from her friends, she comes up with a list of tutorials to watch, as well as the most important minute, a_{i,j} in the video, for the window on the ith row and jth column. However, AngelsandDevsLOL realizes that she cannot focus on more than two things at once!

To solve this issue, she decides to delay watching some videos for some number of minutes so that no two important minutes overlap. She wants to know the number of tutorials that she must delay such that she can study for the CCC without losing focus!

Constraints

1 \le a_{i, j} \le 10^6

1 \le N \le 10^3

1 \le M \le 10^3

Input Specification

The first line will contain integer N, representing the number of rows, and M, representing the number of columns.

The next N lines will contain M numbers, representing the most important minute in the video.

Output Specification

Print out the number of tutorials that must be delayed such that no two important minutes overlap.

Sample Input

3 3
1 2 3
4 2 6
9 100 12479

Sample Output

1

Comments

There are no comments at the moment.