Budget Allocation

Interview

Time limit1sMemory limit128 MB

Summary

Given budget requests and a total cap, find the maximum integer cap value such that capping requests at that value keeps the total within budget.

Level: Medium4 of 10
Topics: Binary search, Greedy
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples2

Example 1
Input
```
4
120 110 140 150
485
```
Expected output
```
127
```
Example 2
Input
```
5
70 80 30 40 100
450
```
Expected output
```
100
```