Description

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.

Input Format

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 Format

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

5 15
2 8
2 10
2 12
2 10
2 5

7

7 15
1 5
2 3
2 5
2 7
2 4
1 5
1 3

9

Hint

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 CONTEST #7 T3 GITARA.

Translated by ChatGPT 5