Energy Tycoon Strategy

Little Vasya is playing a new computer game Energy Tycoon. The board has $n$ slots arranged in a line. There are power plants; each occupies either one slot or two consecutive slots and produces one unit of energy. Each turn, a new power plant appears with a specified size. You may place it on the board if there is free space. If there is no space for the new plant, you may remove some older power plants. After each turn, the number of plants placed on the board is added to the total score.

Vasya knows in advance the type of power plant available on each turn. Your task is to help him determine the maximum total score he can achieve by optimally placing (and possibly removing) power plants during the game.

Note: A power plant of size 1 occupies one slot and a power plant of size 2 occupies two consecutive slots. The plants cannot overlap, and each plant always produces exactly one unit of energy.

inputFormat

The first line contains two integers $n$ and $t$ ($1 \leq n \leq 10^9$, $1 \leq t \leq 10^5$) --- the number of slots on the board and the number of turns, respectively.

The next line contains $t$ integers, each either 1 or 2, where each integer represents the size of the power plant available on that turn.

outputFormat

Output a single integer --- the maximum total score Vasya can achieve if he plays optimally.

sample

3 5
2 1 2 1 1

10