CodeForce--Benches

A. Benches

 

There are $\mathrm{nn benches\; in\; the\; Berland\; Central\; park.\; It\; is\; known\; that aiai people\; are\; currently\; sitting\; on\; the ii-th\; bench.\; Another mm people\; are\; coming\; to\; the\; park\; and\; each\; of\; them\; is\; going\; to\; have\; a\; seat\; on\; some\; bench\; out\; of nn available.}$

Let $\mathrm{kk be\; the\; maximum\; number\; of\; people\; sitting\; on\; one\; bench\; after\; additional mm people\; came\; to\; the\; park.\; Calculate\; the\; minimum\; possible kk and\; the\; maximum\; possible kk.}$

Nobody leaves the taken seat during the whole process.

Input

The first line contains a single integer $\mathrm{nn (1\le n\le 100)(1\le n\le 100) —\; the\; number\; of\; benches\; in\; the\; park.}$

The second line contains a single integer $\mathrm{mm (1\le m\le 10000)(1\le m\le 10000) —\; the\; number\; of\; people\; additionally\; coming\; to\; the\; park.}$

Each of the next $\mathrm{nn lines\; contains\; a\; single\; integer aiai (1\le ai\le 100)(1\le ai\le 100) —\; the\; initial\; number\; of\; people\; on\; the ii-th\; bench.}$

Output

Print the minimum possible $\mathrm{kk and\; the\; maximum\; possible kk,\; where kk is\; the\; maximum\; number\; of\; people\; sitting\; on\; one\; bench\; after\; additional mm people\; came\; to\; the\; park.}$

Examples

input

Copy

4
6
1
1
1
1

output

Copy

3 7

input

Copy

1
10
5

output

Copy

15 15

input

Copy

3
6
1
6
5

output

Copy

6 12

input

Copy

3
7
1
6
5

output

Copy

7 13

Note

In the first example, each of four benches is occupied by a single person. The minimum $\mathrm{kk is 33.\; For\; example,\; it\; is\; possible\; to\; achieve\; if\; two\; newcomers\; occupy\; the\; first\; bench,\; one\; occupies\; the\; second\; bench,\; one\; occupies\; the\; third\; bench,\; and\; two\; remaining\; —\; the\; fourth\; bench.\; The\; maximum kk is 77.\; That\; requires\; all\; six\; new\; people\; to\; occupy\; the\; same\; bench.}$

The second example has its minimum $\mathrm{kk equal\; to 1515 and\; maximum kk equal\; to 1515,\; as\; there\; is\; just\; a\; single\; bench\; in\; the\; park\; and\; all 1010people\; will\; occupy\; it.}$

题目大意：公园里有n个座位，一开始每个座位都有多少人（人数给出），公园里将进来m人，问这些人往座位上坐，那么座位上人数最多的那个能有多少人，最多人数最小化能有多少人？　　

　　自己还是太菜了啊，看了一下大佬的题解，发现思维真的太强了

　　最多能有多少肯定好计算，把数组排序加上将要进来的人数就是，也就是代码中的kmax，问题是如何求得最小化的最大值呢？

　　大佬还是先排序，排好序了，让数组下标从0开始，依次与数组最大值比较（这个比较好理解，因为要是不超过的话肯定数组最大值就是最大啊），

　　然后，如果第i个元素和最大值相等，那么这个元素自增，并且m要自减，下面再来一个循环，只要这个元素比最大值小，那么这个元素就进行自增，m进行自减

　　知道m为0或者这个元素不小于最大值了，如果这轮i==n了但是m还没有为0，那么此时就要重新将i赋值为0

　　结束这层循环以后，要在外层循环中再次对数组进行排序，这个目的是为了更新最大值,最后输出就ok了

#include<iostream>
#include<algorithm>
using namespace std;
int arr[101];
int n,m;
int kmax;
void solve()
{
    int i=0;
    sort(arr,arr+n);
    kmax=arr[n-1]+m;
    while(m!=0)
    {
    if(arr[i]==arr[n-1]&&m!=0)
    {
        arr[i]++;
        m--;
    }
    while(arr[i]<arr[n-1]&&m!=0)
    {
        arr[i]++;
        m--;
    }
    i++;
    if(i==n)
    i=0;
    }
    i=0;
    sort(arr,arr+n);//更新最大值 
}
int main()
{
    while(cin>>n>>m)
    {
        for(int i=0;i<n;i++)
        cin>>arr[i];
        solve();
        cout<<arr[n-1]<<" "<<kmax<<endl;
    }
    return 0;
}