#A3005. GITARA

GITARA

题目背景

Darko 有一个想象的外星朋友,他有十亿根手指。外星人快速拿起吉他,在网上找到一段简单的旋律并开始弹奏。

这个吉他像寻常一样有六根弦,令其用 1166 表示。每根弦被分成 PP 段,令其用 11PP 表示。

旋律是一串的音调,每一个音调都是由按下特定的一根弦上的一段而产生的(如按第 44 弦第 88 段)。如果在一根弦上同时按在几段上,产生的音调是段数最大的那一段所能产生的音调。

例:对于第 33 根弦,第 55 段已经被按,若你要弹出第 77 段对应音调,只需把按住第 77 段,而不需放开第 55 段,因为只有最后的一段才会影响该弦产生的音调(在这个例子中是第 77 段)。类似,如果现在你要弹出第 22 段对应音调,你必须把第 55 段和第 77 段都释放。

请你编写一个程序,计算外星人在弹出给定的旋律情况下,手指运动的最小次数。

题目描述

你有一个 6×P6 \times P 的矩阵 AA,初始状态皆为 00

对于所有要求 (i,j)(i,j)

你需要满足要求:

  1. 此时 Ai,jA_{i,j} 状态为 11

  2. 对于 Ai,j+k(k>0)A_{i,j+k} (k>0) 状态为 00

你在满足要求的情况下需要求状态转换最小次数。

输入格式

第一行包含两个正整数 nnPP。它们分别指旋律中音调的数量及每根弦的段数。

下面的 nn 行每行两个正整数 iijj,分别表示能弹出对应音调的位置——弦号和段号,其为外星人弹奏的顺序。

输出格式

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

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

提示

样例 1 解释

所有的音调都是由第二根弦产生的。首先按顺序按 88 1010 1212count=3count=3)。然后释放第 1212 段(count=4count=4)。最后,按下第 55 段,释放第 88 1010 段 (count=7count=7)。

样例 2 解释

对于每个操作,分别需要 11 11 11 11 33 00 22 次手指运动。

数据规模及约定

按下或释放一段弦各计一次手指运动。弹弦不算手指的移动,而是一个弹吉他的动作。(指你不需要管他怎么弹的,只需要按就是啦,说不定他可以用超能力呀)

对于 100%100\% 的数据 n5×105n \le 5 \times 10^52P3×1052 \le P \le 3 \times 10^5

说明

本题满分 7070 分。

译自 COCI2010-2011 CONTEST #7 T3 GITARA