Summer Institute '17 Contest 1 P6 - Fortunate Farmland

View as PDF

Submit solution

Points: 10
Time limit: 1.4s
Memory limit: 256M

Problem types

The country of Fortunate Farmland judges its success differently than most nations. Rather than wanting to achieve a maximum GDP or maximize the number of millionaires in the country, the country aims to maximize the minimum income of its citizens. In order to improve this minimum value, the country has a fund set aside (collected from taxes) and will use all the money in that fund to raise incomes in such a way as to maximize the minimum income of all citizens. Take the following small example. Let's say that there are 10 citizens with the following initial incomes in Farmland Dollars: 12, 8, 3, 9, 15, 22, 27, 13, 77 and 18. Now, let's say that the Fortunate Farmland government has a total of 30 Farmland Dollars to distribute amongst its citizens. Note that we can only pay integer amounts of Farmland Dollars to each citizen. The government would pay 3 Farmland Dollars to the first person, 7 to the second person, 12 to the third person, 6 to the fourth person and 2 to the 8th person. After these payments, the new income list (in Farmland Dollars) would be: 15, 15, 15, 15, 15, 22, 27, 15, 77 and 18. Now, the minimum income of any citizen is 15 Farmland Dollars.

Given the initial incomes of each citizen in Fortunate Farmland as well as how much money the government of Fortunate Farmland has to distribute to each citizen (in integer increments of Farmland Dollars), determine the minimum income of any citizen of Fortunate Farmland after the money has been distributed. As previously stated, the government of Fortunate Farmland always distributes this money in such a way as to maximize the minimum income of its citizens, within the restrictions of giving integer Farmland Dollars to some of its citizens.

Input Specification

The first line of input will contain two space-separated positive integers, c (c \le 10^5), representing the number of citizens of Fortunate Farmland and t (t \le 10^{12}, t/c \le 10^9), the amount Farmland Dollars to be distributed amongst the citizens. The following c lines contain one positive integer each, m_i (m_i \le 10^9), representing the income of the ith citizen of Fortunate Farmland in Farmland Dollars.

Output Specification

Output a single line with the minimum income amongst all the citizens of Fortunate Farm after the government makes its distribution.

Sample Input 1

10 30
12
8
3
9
15
22
27
13
77
18

Sample Output 1

15

Sample Input 2

5 100
1
2
3
4
10

Sample Output 2

24

Comments

There are no comments at the moment.