Decorations#10267
In Potokolandia, there are distinct types of Christmas tree decorations, each labeled with an integer from to . The quantity of decorations of type 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 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 decorations and one pair of type 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 pairs of the same type.
The first line contains two integers and (1\le n,k\le 10^5).
The second line contains integers a_1,a_2,\dots,a_n (1\le a_i\le 10^5).
Output a single integer — the minimum number of decorations Grandpa Frost needs to draw to guarantee a New Year-beautiful set.
Example 1
In the first example, if Grandpa draws decorations from the pile, he will always be able to form pairs of decorations of the same type.