COCI 2010/2011 contest#7- 기타 연주(GITARA) > 문제은행 : 정보올림피아드&알고리즘




2443 : 기타 연주(GITARA)

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
7 회   
시도횟수
17 회   

문제

영호는 최근 손가락을 1억개나 가지고 있는 상상속의 외계인 친구를 알게 되었다. 이 외계인 친구는 기타를 가지고 있었고 영호를 위해 연주를 시작했다.


아래 그림과 같이 기타는 일반적으로 6개의 줄을 가지고 있다. 각 줄을 편의상 1번에서 6번 으로 부르기로 한다. 또한 각 줄은 프렛을 공유하여 가지고 있다. 각각의 프렛을 편의상 1번에서 P번으로 부르기로 한다.


 


 



 


멜로디(소리의 높낮이)는 프렛를 누르는 것에 따라 다르게 나온다. 물론 프렛과 프렛사이를 손라락으로 누른뒤 해당 줄을 튕겨 소리를 내는 것이 일반적이다. 문제에서는 편의상 프렛의 위치를 누르는 것으로 한다.


하나의 줄에서 여러개의 프렛을 누르게 되면 그 중 가장 높은 음만 나오게 된다. 예를 들어 2번 줄에 2번 프렛, 3번 프렛, 6번 프렛을 함께 누르고 2번 줄을 튕기게 되면 6번 프렛에 해당하는 음만 나온다는 것이다. 이 상태에서 3번 프렛에 해당하는 음을 내고 싶다면 6번 프렛을 누르고 있던 손가락을 떼야 한다. 외계인 친구는 한번에 하나의 음만 낸다. 하지만 손가락이 많으므로 여러개의 프렛을 계속 누르고 있을 수가 있다.(힘도 세다.^^)


외계인 친구가 주어진 멜로디를 낼 때 누르거나 떼는 횟수의 최소값을 구하는 프로그램을 작성하시오. 기타줄을 튕기는 것은 횟수에 포함시키지 않는다.


입력형식

첫 행에 멜로디의 수를 나타내는 N(N≤500,000) 과 프랫의 수를 나타내는 P(2≤P≤300,000)가 입력된다.

이후 N 행에 걸쳐 줄 번호(줄은 6개 밖에 없다.)와 프렛 번호가 공백으로 구분되어 입력된다.


출력형식

외계인 친구가 주어진 멜로디를 낼 때 누르거나 떼는 횟수의 최소값을 출력한다.


입력 예

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

출력 예

7

Hint!

입력 예 2
7 15
1 5
2 3
2 5
2 7
2 4
1 5
1 3

출력 예 2
9




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP