题干：

There are 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 kk be the maximum number of people sitting on one bench after additional mmpeople 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 nn (1≤n≤100)(1≤n≤100) — the number of benches in the park.

The second line contains a single integer mm (1≤m≤10000)(1≤m≤10000) — the number of people additionally coming to the park.

Each of the next nn lines contains a single integer aiai (1≤ai≤100)(1≤ai≤100) — the initial number of people on the ii-th bench.

Output

Print the minimum possible 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

4
6
1
1
1
1

Output

3 7

Input

1
10
5

Output

15 15

Input

3
6
1
6
5

Output

6 12

Input

3
7
1
6
5

Output

7 13

Note

In the first example, each of four benches is occupied by a single person. The minimum 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 kk equal to 1515 and maximum kk equal to 1515, as there is just a single bench in the park and all 1010 people will occupy it.

解题报告：

   maxx很好弄，全加在那个最大的上就可以了。（也就是最大可能的最大值）

  主要是minn：（最小可能的最大值）

    这题做法很多，可以直接优先队列模拟，这种题见过很多个了。

    还有一个方法，因为要输出最小的最大值，所以直接看看能不能把其余的都变成最大的，然后剩下的再均摊。如果不够都变成最大的，那最大的那个就是答案。

    刚开始有一个错误的想法，就是上来就平均分，然后剩余的多的再加到最小的身上。这样错误想法的产生，就是因为没有注意到答案的特点：肯定要大于等于那个最大的。

AC代码：

#include<bits/stdc++.h>

using namespace std;
int n,m;
int a[1000 + 5];
priority_queue<int,vector<int>,greater<int> > pq;
int main()
{
	cin>>n>>m;
	for(int i = 1; i<=n; i++) scanf("%d",a+i),pq.push(a[i]);
	sort(a+1,a+n+1);
	int maxx = a[n] + m;
	int minn = 0;
	for(int i = 1 ; i<=m; i++) {
		int cur = pq.top();pq.pop();
		pq.push(cur+1);
	}
	for(int i = 1; i<=n; i++) {
		minn = max(minn,pq.top());pq.pop();
	}
	printf("%d %d\n",minn,maxx);
    return 0;
}

当时的错误想法：

//	for(int i = 1; i<=n; i++) a[i]+=(m/n);
//	m%=n;
//	for(int i = 1; i<=m; i++) a[i]++;
//	minn = *max_element(a+1,a+n+1);

总结：先分析清楚问题，再动手敲代码。