題干：

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：（最小可能的最大值）

? ? 這題做法很多，可以直接優(yōu)先隊(duì)列模擬，這種題見過很多個了。

? ? 還有一個方法，因?yàn)橐敵鲎钚〉淖畲笾?#xff0c;所以直接看看能不能把其余的都變成最大的，然后剩下的再均攤。如果不夠都變成最大的，那最大的那個就是答案。

? ? 剛開始有一個錯誤的想法，就是上來就平均分，然后剩余的多的再加到最小的身上。這樣錯誤想法的產(chǎn)生，就是因?yàn)闆]有注意到答案的特點(diǎn)：肯定要大于等于那個最大的。

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; }

當(dāng)時的錯誤想法：

// 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);

總結(jié)：先分析清楚問題，再動手敲代碼。

總結(jié)

以上是生活随笔為你收集整理的【CodeForces - 1042A】Benches （优先队列，思维模拟，maxmin问题）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。