Description

You have $n$ types of cards. The number of cards of type $i$ is $c_i$. There is also a special card type: joker, and its number is $m$.

You can form one set of cards by taking one card from each type. You can also form one set by taking one joker and one card from every other type except one specific type. For example, when $n=3$, there are $4$ valid sets in total: $\{1,2,3\}$, $\{J,2,3\}$, $\{1,J,3\}$, $\{1,2,J\}$.

Given $n$, $m$, and $c_i$, your task is to form as many sets as possible. Each card can be used in at most one set (you may leave some cards unused).

Input Format

The first line contains two integers $n$, $m$, representing the number of card types and the number of jokers.

The second line contains $n$ integers $c_i$, representing the number of cards of each type.

Output Format

Output only one integer: the maximum number of sets that can be formed.

3 4
1 2 3

3

Hint

Sample Explanation

The input shows that there are $1$ card of type $1$, $2$ cards of type $2$, $3$ cards of type $3$, and $4$ jokers. At most three sets can be formed: $\{1,J,3\}$, $\{J,2,3\}$, $\{J,2,3\}$. One joker remains, and all other cards are used up.

Constraints

For $50\%$ of the testdata, $2 \le n \le 5$, $0 \le m \le 10^6$, $0 \le c_i \le 200$.

For $100\%$ of the testdata, $2 \le n \le 50$, $0 \le m,c_i \le 5 \times 10^8$.

Translated by ChatGPT 5