##### ACSL Practice 2009

You are asked to design a *compression scheme* for transmitting fax
images of documents. After an image is scanned in using a scanner, you
obtain a sequence of numbers where each number takes a value from
to . For example, an image may be converted into a sequence of the
form

Since it is not necessary to transmit the exact image, you decide to discretize each number to levels, namely and , so that you can code each level using only bits as follows:

Level | ||||

Code | `00` |
`01` |
`10` |
`11` |

Then you realize that large areas of the same value (e.g. white) often occur in documents resulting in long sequences of very similar numbers. You decide to adopt a compression scheme as follows:

- For the first number in the sequence, you will use the bits as described previously.
- For all other numbers:
- if the previous number is the same as the current number, you
will transmit the bit
`0`

. - otherwise, you will transmit the bit
`1`

followed by the -bit code of the number. That is,`1`

followed by`00`

for number`1`

followed by`01`

for number`1`

followed by`10`

for number`1`

followed by`11`

for number

- if the previous number is the same as the current number, you
will transmit the bit

Finally, since you are not worried about a small amount of error, you
realize that you can improve your scheme by ignoring isolated changes.
For example, if the input sequence is and you
transmit the sequence , the total error will be
and the string that needs to be
transmitted is `0000001011000`

. If, instead you choose to transmit the
sequence , the total error will be
, but the string that needs to be
transmitted would be `000000000`

which is shorter.

You decide to measure the overall cost of a transmission by the following weighted sum

where

- the weight can be adjusted to give more emphasis to either the total error or the total number of bits transmitted
- for an input sequence and a transmitted sequence , both of length , the total error is .

**Example.** For the input sequence with ,

- we can transmit the sequence
by transmitting the string
`0000001011000`

with a cost of ; - or we can transmit the sequence
by transmitting the string
`000000000`

with a cost of .

In this case, the second option has lower cost.

#### Input Specification

The input consists of several lines. The first line contains two integers and in this order. Integer denotes the length of the input sequence and integer is the weight. Each of the subsequent lines contains an integer of the sequence.

#### Output Specification

The output contains a single integer which is the smallest possible cost required to transmit the input sequence with the given value of .

#### Sample Input

```
8 100
2
2
2
2
2
46
2
2
```

#### Sample Output

`952`

## Comments