Background

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.

Problem 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