Budget Allocation

A country must review budget requests from several regions and allocate money within a fixed national budget. If the sum of all requested amounts is at most the total budget, every region receives exactly the amount it requested.

Otherwise, choose one integer upper limit. A region whose request is greater than this limit receives only the limit, while a region whose request is at most the limit receives its requested amount. The total allocated amount must not exceed the national budget, and it should be as large as possible.

Given the requested budgets of all regions and the total national budget, find the maximum amount allocated to any one region.

The first line contains an integer N, the number of regions. N is between 3 and 10,000 inclusive.

The second line contains N integers separated by spaces, representing the requested budgets of the regions. Each request is between 1 and 100,000 inclusive.

The third line contains an integer M, the total national budget. M is between N and 1,000,000,000 inclusive.

Print one integer: the maximum allocated budget among all regions in an allocation satisfying the conditions.