I. Decorations

In Potokolandia, there are $n$ distinct types of Christmas tree decorations, each labeled with an integer from $1$ to $n$. The quantity of decorations of type $i$ is denoted as $a_i$.

Grandpa Frost has collected all these decorations into a single pile and will randomly draw one decoration at a time. A set of drawn decorations is considered New Year-beautiful if it contains at least $k$ pairs of decorations of the same type. For instance, from the set $\{1,2,1,2,1,1,3\}$ (where identical numbers indicate decorations of the same type), a maximum of three pairs can be formed: two pairs of type $1$ decorations and one pair of type $2$ decorations.

Your task is to help Grandpa Frost determine the minimum number of decorations he must draw from the pile to ensure he has a New Year-beautiful set. It is guaranteed that if Grandpa draws all the decorations from the pile, he will be able to form at least $k$ pairs of the same type.

Input

The first line contains two integers $n$ and $k$ ($1\le n,k\le 10^5$).

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^5$).

Output

Output a single integer — the minimum number of decorations Grandpa Frost needs to draw to guarantee a New Year-beautiful set.

Examples

Note

In the first example, if Grandpa draws $6$ decorations from the pile, he will always be able to form $2$ pairs of decorations of the same type.