2512번

2512

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int getSum(vector<int> v, int num) {
	int sum = 0;
	for (int i = 0; i < v.size(); i++) {
		sum += min(v[i], num);
	}
	return sum;
}

int main() {
	int n, m;
	vector<int> v;
	cin >> n;

	int maxnum = 0;
	for (int i = 0; i < n; i++) {
		int input;
		cin >> input;
		v.push_back(input);
		maxnum = max(maxnum, input);
	}

	cin >> m;

	int start = 1;
	int end = maxnum;
	int mid = (start + end) / 2;


	int answer = 0;
	while (start <= end) {
		int sum = getSum(v, mid);
		if (sum > m) {
			end = mid - 1;
			mid = (start + end) / 2;
		}
		else {
			if (answer <= sum) {
				answer = mid;
			}
			start = mid + 1;
			mid = (start + end) / 2;
		}
	}
	cout << answer;
}