Description

你有 \(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\), 你的任务是组成尽量多的套牌. 每张牌最多只能用在一副套牌里 (可以有牌不使用).

Input

第一行包含两个整数 \(n, m\), 即牌的种数和 joker 的个数;

第二行包含 \(n\) 个整数 \(c_i\), 即每种牌的张数.

Output

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

Sample Input

3 4
1 2 3

Sample Output

3

Data Range

50% 的数据满足:\(2 \leq n \leq 5, 0 \leq m \leq 10^6, 0 \leq c_i \leq 200\);

100% 的数据满足:\(2 \leq n \leq 50, 0 \leq m, c_i \leq 5 \times 10^8\).

Explanation

Joker 可以瞎用, 但是不能单独用.

所以优先用完 Joker~

然后再把其他的用完.

是个二分答案加 \(O(n)\) 判定.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;

int n, m, a[51], res;

bool judge(int x)
{
    int t = min(m, x);
    for (int i = 1; i <= n; i++)
        if (a[i] < x) {
            t -= (x - a[i]);
            if (t < 0)
                return false;
        }
    return true;
}

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    int l = 1, r = 1000000000, res = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (judge(mid)) {
            res = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    printf("%d\n", res);
    return 0;
}