def solution(budgets, M):
    budgets.sort()
    # 최대값을 지정하기 위해 정렬을 했지만 정렬보단 max 함수가 시간 복잡도가 더 작으므로 max를 활용할것.
    start = 0
    end = budgets[-1]
    result = 0
    while start <= end:
        mid = (start + end) // 2
        sum_bud = 0
        # 여기선 모든 지방에 분배한 예산의 총합이 주어진 예산 한도보다 크면 안되기때문에 mid값과 각 지방의 요청 예산을 비교해서 sum_bud에 각 지방에 사용한 예산의 누적값을 저장할 것임.
        for bud in budgets:
            if bud >= mid:
                # 요청한 예산이 mid값보다 크거나 같은 경우 mid값만큼만 배분함.
                sum_bud += mid
            else:
                # 요청한 예산이 mid값보다 작은 경우 요청한 만큼만 배분함.
                sum_bud += bud
        if sum_bud <= M:
            # 각 지방에 배분한 예산의 누계가 예산 한도보다 작을 경우 -> 즉, 문제에서 요구하는 조건과 일치한 경우 result에 이번에 쓴 mid값을 저장하고 최소값을 증가시켜서 다시 한번 탐색해보도록 한다.
            start = mid + 1
            result = mid
        else:
            # 예산한도를 초과한 경우 -> 조건을 달성하지 못했으므로 이 경우엔 mid값을 저장하지 않고 탐색 범위만 줄여주도록 한다.
            end = mid - 1
    return result

# 백준에서 한번 풀었던 문제
# 이분탐색의 핵심을 다시 짚어보고 가자.
# 이분 탐색의 핵심은 최소, 최대, 중간값임.
# 문제를 차근차근 읽어보고 최소, 최대, 중간값을 정한 뒤 중간값을 무엇과 비교할 것이고, 비교해서 나온 결과를 어떻게 저장할 것인지도 정해야함..
# 비교해서 나온 최종 결과값을 무엇과 비교할 것인지도 정해야 하며, 비교한 결과에 따라 최소값을 조정할 것인지 최대값을 조정할 것인지도 판단할 수 있어야함.
