P6704 [COCI 2010/2011 #7] GITARA

Darko 有一个想象的外星朋友，他有十亿根手指。外星人快速拿起吉他，在网上找到一段简单的旋律并开始弹奏。 这个吉他像寻常一样有六根弦，令其用 $1$ 到 $6$ 表示。每根弦被分成 $P$ 段，令其用 $1$ 到 $P$ 表示。 旋律是一串的音调，每一个音调都是由按下特定的一根弦上的一段而产生的（如按第 $4$ 弦第 $8$ 段）。如果在一根弦上同时按在几段上，产生的音调是段数最大的那一段所能产生的音调。 例：对于第 $3$ 根弦，第 $5$ 段已经被按，若你要弹出第 $7$ 段对应音调，只需把按住第 $7$ 段，而不需放开第 $5$ 段，因为只有最后的一段才会影响该弦产生的音调(在这个例子中是第 $7$ 段)。类似，如果现在你要弹出第 $2$ 段对应音调，你必须把第 $5$ 段和第 $7$ 段都释放。 请你编写一个程序，计算外星人在弹出给定的旋律情况下，手指运动的最小次数。

你有一个 $6 \times P$ 的矩阵 $A$，初始状态皆为 $0$。 对于所有要求 $(i,j)$，你需要满足要求： 1. 此时 $A_{i,j}$ 状态为 $1$； 2. 对于 $A_{i,j+k}\ (k>0)$ 状态为 $0$。 你需要求在满足要求的情况下状态转换最小次数。

第一行包含两个正整数 $n,P$。它们分别指旋律中音调的数量及每根弦的段数。 接下来 $n$ 行，每行两个正整数 $i,j$，分别表示能弹出对应音调的位置——弦号和段号，其为外星人弹奏的顺序。

一个非负整数表示外星人手指运动次数最小值。

#### 样例 1 解释 所有的音调都是由第二根弦产生的。首先按顺序按 $8,10,12$（$count=3$）。然后释放第 $12$ 段（$count=4$）。最后，按下第 $5$ 段，释放第 $8,10$ 段（$count=7$）。 #### 样例 2 解释 对于每个操作，分别需要 $1,1,1,1,3,0,2$ 次手指运动。 #### 数据规模及约定 按下或释放一段弦各计一次手指运动。弹弦不算手指的移动，而是一个弹吉他的动作。（指你不需要管他怎么弹的，只需要按就是啦，说不定他可以用超能力呀） 对于 $100\%$ 的数据，$n \le 5 \times 10^5$ ，$2 \le P \le 3 \times 10^5$。 #### 说明 本题满分 $70$ 分。 译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #7](https://hsin.hr/coci/archive/2010_2011/contest7_tasks.pdf) T3 GITARA