P6704 [COCI 2010/2011 #7] GITARA

Darko has an imaginary alien friend who has one billion fingers. The alien quickly picks up a guitar, finds a simple melody online, and starts playing it. The guitar, as usual, has six strings, labeled from $1$ to $6$. Each string is divided into $P$ frets (segments), labeled from $1$ to $P$. A melody is a sequence of notes. Each note is produced by pressing a certain fret on a certain string (for example, string $4$ fret $8$). If multiple frets are pressed on the same string at the same time, the produced note is the one corresponding to the largest fret number among those pressed. Example: On string $3$, if fret $5$ is already pressed and you want to play the note at fret $7$, you only need to press fret $7$ and do not need to release fret $5$, because only the highest pressed fret affects the note produced by that string (in this example, fret $7$). Similarly, if you now want to play the note at fret $2$, you must release both fret $5$ and fret $7$. Please write a program to compute the minimum number of finger movements needed for the alien to play the given melody.

You have a $6 \times P$ matrix $A$, and initially all entries are $0$. For each required position $(i, j)$, you must satisfy: 1. At that moment, $A_{i, j}$ is $1$. 2. For $A_{i, j+k}$ where $k>0$, the value is $0$. You need to find the minimum number of state changes while satisfying all requirements.

The first line contains two positive integers $n, P$, which represent the number of notes in the melody and the number of frets on each string. The next $n$ lines each contain two positive integers $i, j$, representing the position (string number and fret number) that can produce the corresponding note, in the order played by the alien.

Output one non-negative integer: the minimum number of finger movements made by the alien.

#### Explanation for Sample 1 All notes are produced on the second string. First press frets $8, 10, 12$ in order ($count=3$). Then release fret $12$ ($count=4$). Finally, press fret $5$ and release frets $8, 10$ ($count=7$). #### Explanation for Sample 2 For each operation, the required numbers of finger movements are $1, 1, 1, 1, 3, 0, 2$. #### Constraints Pressing or releasing a fret counts as one finger movement. Plucking the string does not count as a finger movement; it is a guitar-playing action (meaning you do not need to care how it is plucked, only the pressing is considered. Maybe the alien can use superpowers.) For $100\%$ of the testdata, $n \le 5 \times 10^5$, $2 \le P \le 3 \times 10^5$. #### Notes This problem is worth $70$ points in total. Translated from [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #7](https://hsin.hr/coci/archive/2010_2011/contest7_tasks.pdf) T3 GITARA. Translated by ChatGPT 5