Background

The problem statement itself is the best background ().

Problem Description

Students do exercises every day, and they will pass through the spinning stairs.

The spinning stairs has $n+1$ steps. For step $i \ (1\le i\le n+1)$, it has a spinning value $a_i$, where $a_i\in\{0,1\}$. In particular, $a_{n+1}=0$.

For a step $i$, if the spinning value of the next step is the same as it (that is, $a_{i+1}=a_i$), then we can walk down directly, costing $1$ second. Otherwise, we need to spend $1$ second to spin once to change the spinning value of the current step to $1-a_i$, and then spend another $1$ second to walk down.

We need to do exercises for $k$ days. Every day, we walk from step $1$ to step $n+1$.

Please compute the total time for these $k$ days that students spend on the spinning stairs.

Input Format

The input has $2$ lines.

The first line contains two numbers $n$ and $k$.

The second line contains $n$ integers. The $i \ (1\leq i\leq n)$-th number represents $a_i$.

Output Format

Output one integer in one line, representing the total time spent on the spinning stairs over these $k$ days.

3 2
0 1 0

9

Hint

Sample Explanation

On the first day, the sequence is $a=\{0,1,0\}$. We walk $3$ steps and spin $2$ times, so the time is $5$.

On the second day, the sequence is $a=\{1,0,0\}$. We walk $3$ steps and spin $1$ time, so the time is $4$.

Constraints

This problem uses subtasks for bundled judging. The score for each subtask is as follows: | Subtask | Range | Score | | :----------: | :----------: | :----------: | | $0$ | $1\le n,k\le 2\times 10^3$ | $30$ | | $1$ | $1\le n,k\le 2\times 10^6$ | $70$ |

For all data, $1\le n,k\le2\times10^6$ and $a_i\in\{0,1\}$.

Translated by ChatGPT 5