Water supply cap
Statement
An irrigation cooperative has a fixed total of M water to hand out to its farms this year. There are N farms in the cooperative, and every farm has already filed a request for the amount of water it needs this year.
The cooperative picks one cap and hands out water as follows. A farm whose request is at most the cap receives its request in full. A farm whose request is larger than the cap receives only the cap. The cap is set as a natural number, and the same cap applies to every farm.
The total water handed out cannot go over the M the cooperative holds. The cooperative wants to give the farms as much water as it can, so it sets the cap as high as it can while the total stays within M. Raising the cap above the largest request changes nothing about what is handed out, so when every farm can receive its request in full, the answer is the largest of the requests.
Write a program that, given the amount of water each farm requested and the total supply M, finds the largest cap that can be used.
For example, suppose the amounts of water requested by N=4 farms are as in the following table and the total supply M is 485.
| Farm | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Amount requested | 120 | 110 | 140 | 150 |
With the cap at 127, farms 1 and 2 have requests smaller than the cap, so they receive their requests in full, and farms 3 and 4 each receive the cap of 127. The total handed out is 484, which does not go over 485. Raising the cap one step to 128 makes the total 486, which does go over 485.
| Cap | Farm 1 | Farm 2 | Farm 3 | Farm 4 | Total handed out |
|---|---|---|---|---|---|
| 127 | 120 | 110 | 127 | 127 | 484 |
| 128 | 120 | 110 | 128 | 128 | 486 |
The answer in this example is therefore 127.
There are also cases where the requests add up to at most M. In those cases every farm receives its request in full, so the largest of the requests becomes the answer.
Input and Output Examples
Example 1
Input
4 120 110 140 150 485
Output
127
Example 2
Input
5 70 80 30 40 100 450
Output
100
Example 3
Input
1 264 324
Output
264
Input
The number of farms N is given first, on the first line. N is a natural number from 1 to 10,000.
The second line then holds the amount of water each farm requested, from farm 1 through farm N in order, separated by one space. Each request is a natural number from 1 to 100,000.
The third line then holds the total supply M. M is a natural number from 1 to 2,000,000,000.
Output
Print the largest cap that can be used on the first line.
Print one number and then a newline. Do not attach any other character or space before or after it.
Requirements
- Read the input from standard input and write the answer to standard output
- The cap is a natural number, and the same cap applies to every farm
- A farm whose request is at most the cap receives its request in full
- If every farm can receive its request in full, print the largest of the requests
- The input is three lines. N comes on the first line, the N requests on the second line, and M on the third line
- The output is one number and a newline, nothing else
- Grading compares the output with the expected value down to the last character
- You must write a program that reads from standard input and writes to standard output
- Trailing spaces at the end of a line and blank lines at the end of the output are ignored when grading
- The languages you can use are Python and JavaScript
- The memory limit is 256MB. The browser does not measure it, it only states it
- The time limit is set by measuring the setter's reference solution on the same runtime
- On this problem you submit code, not a prompt. That code runs in the browser on this device, and all that goes to the server is a fingerprint of the output and the time it took. Whether it is correct is decided by the server. The run time is a number each device reports, so the code and the device details are posted next to it on the leaderboard.
- There are 16 cases, and 3 of them show the input together with the expected output. The rest are used only when you submit and are not shown on this page.
- You have to pass all 16 cases to solve this.
Examples
3 public cases. Judging also uses hidden cases. You have to pass all 16 cases to solve this.
1 264 324
264
4 120 110 140 150 485
127
5 70 80 30 40 100 450
100
Solution
Your code runs on this device. Only the fingerprint of the output and the elapsed time go to the server. The server decides whether it is correct.
Submitting requires you to log in. Running against the public cases works without one.
You can test with 3 public cases. Submitting runs the hidden cases too.
People who solved this problem
The time shown is the time spent solving. Input reading time is outside the solver's control, so it is excluded. And since each device reports this value itself, we record which device measured it.
Log in and you can see the code once you solve this problem.