## COCI '10 Contest 7 #3 Gitara

View as PDF

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem types

Darko has a new imaginary extraterrestrial friend with a billion fingers. The extraterrestrial has soon taken hold of his guitar, found a simple melody online, and started playing it.

The guitar, as usual, has six strings denoted by numbers through . Each string is divided into frets denoted by numbers through .

A melody is a sequence of tones, where each tone is produced by picking a string pressed on a specific fret (e.g., string pressed on the fret). If a string is pressed on several frets, the produced tone will be the one corresponding to the highest of those frets.

For instance, if the string is already pressed on the fret, and the tone which corresponds to the fret is to be produced, the string can be pressed on the fret and picked without releasing the fret, since only the highest one affects the tone produced ( in this case). Similarly, if a tone that corresponds to the fret on the same string is next to be produced, it is necessary to release both and frets.

Write a program which computes the minimum number of finger movements needed to produce the given melody. Note that press or release a single fret counts as one finger move. String picking does not count as a finger move, but rather a guitar pick move.

#### Input Specification

The first line of input contains two positive integers separated by a single space, and . They represent the number of tones in the melody and the number of frets, respectively.

The following lines describe the fields for the corresponding tones – the ordinal of the string and the ordinal of the fret, respectively, in the same order as the extraterrestrial plays them.

#### Output Specification

In a single line of output, print the minimum number of finger movements.

#### Sample Input 1

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

#### Sample Output 1

7

#### Explanation for Sample Output 1

All the tones played are produced by picking the string. First, the frets , , are pressed, in order (three movements). Then, the fret is released to produce the second tone again (fourth movement). Finally, the fret is pressed followed by the release of frets and (a total of seven movements).

#### Sample Input 2

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

#### Sample Output 2

9

#### Explanation for Sample Output 2

, , , , , , finger movements are necessary, in the order of the seven tones produced.