[CQOI2010] 扑克牌

题目描述

你有 $n$ 种牌,第 $i$ 种牌的数目为 $c_i$。另外有一种特殊的牌:joker,它的数目是 $m$。你可以用每种牌各一张来组成一套牌,也可以用一张 joker 和除了某一种牌以外的其他牌各一张组成 $1$ 套牌。比如,当 $n=3$ 时,一共有 $4$ 种合法的套牌:$\{1,2,3\}$,$\{J,2,3\}$,$\{1,J,3\}$,$\{1,2,J\}$。 给出 $n$,$m$ 和 $c_i$,你的任务是组成尽量多的套牌。每张牌最多只能用在一副套牌里(可以有牌不使用)。

输入输出格式

输入格式


第一行包含两个整数 $n$,$m$,即牌的种数和 joker 的个数。 第二行包含 $n$ 个整数 $c_i$,即每种牌的张数。

输出格式


输出仅一个整数,即最多组成的套牌数目。

输入输出样例

输入样例 #1

3 4
1 2 3

输出样例 #1

3

说明

**样例说明** 输入数据表明:一共有 $1$ 个 $1$,$2$ 个 $2$,$3$ 个 $3$,$4$ 个 joker。最多可以组成三副套牌:$\{1,J,3\}$,$\{J,2,3\}$,$\{J,2,3\}$,joker 还剩一个,其余牌全部用完。 **数据范围** 对于 $50\%$ 的数据,$2 \le n \le 5$,$0 \le m \le 10^6$,$0 \le c_i \le 200$。 对于 $100\%$ 的数据,$2 \le n \le 50$,$0 \le m,c_i \le 5 \times 10^8$。