#812. 1816. [CQOI2010]扑克牌

1816. [CQOI2010]扑克牌

[CQOI2010]扑克牌

题目描述

你有 nn 种牌,第i种牌的数目为 cic_i。另外有一种特殊的牌:joker,它的数目是 mm。你可以用每种牌各一张来组成一套牌,也可以用一张 joker 和除了某一种牌以外的其他牌各一张组成 11 套牌。比如,当 n=3n=3 时,一共有 44 种合法的套牌:{1,2,3}\{1,2,3\}{J,2,3}\{J,2,3\}{1,J,3}\{1,J,3\}{1,2,J}\{1,2,J\}

给出 nnmmcic_i,你的任务是组成尽量多的套牌。每张牌最多只能用在一副套牌里(可以有牌不使用)。

输入格式

第一行包含两个整数 nnmm,即牌的种数和 joker 的个数。

第二行包含 nn 个整数 cic_i,即每种牌的张数。

输出格式

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

样例 #1

样例输入 #1

3 4
1 2 3

样例输出 #1

3

提示

样例说明

输入数据表明:一共有 11112222333344 个 joker。最多可以组成三副套牌:{1,J,3}\{1,J,3\}{J,2,3}\{J,2,3\}{J,2,3}\{J,2,3\},joker 还剩一个,其余牌全部用完。

数据范围

对于 50%50\% 的数据,2n52 \le n \le 50m1060 \le m \le 10^60ci2000 \le c_i \le 200

对于 100%100\% 的数据,2n502 \le n \le 500m,ci5×1080 \le m,c_i \le 5 \times 10^8