예산 배정
면접 대비시간 제한1초메모리 제한128 MB
각 지역의 요청 예산과 총 예산이 주어질 때, 요청액을 상한선으로 잘라서 합산한 값이 총 예산을 넘지 않도록 하는 최대 상한선을 구합니다.
문제
국가는 여러 지방의 예산 요청을 검토해 한정된 총예산 안에서 예산을 배정해야 한다. 모든 요청 금액의 합이 총예산 이하라면 각 지방에는 요청한 금액을 그대로 배정한다.
그렇지 않다면 정수 상한액을 하나 정한다. 요청 금액이 상한액보다 큰 지방에는 상한액만 배정하고, 요청 금액이 상한액 이하인 지방에는 요청한 금액을 그대로 배정한다. 이때 배정 금액의 총합이 총예산을 넘지 않으면서 가능한 한 크게 되도록 해야 한다.
각 지방의 요청 금액과 총예산이 주어질 때, 배정된 예산 중 최댓값을 구하시오.
입력
첫째 줄에 지방의 수를 나타내는 정수 N이 주어진다. N은 3 이상 10,000 이하이다.
둘째 줄에는 각 지방의 예산 요청을 나타내는 N개의 정수가 공백으로 구분되어 주어진다. 각 요청 금액은 1 이상 100,000 이하이다.
셋째 줄에는 총예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다.
출력
첫째 줄에 조건을 만족하는 배정 결과에서 배정된 예산 중 최댓값을 출력한다.