Problem Statement

There are n particles present in a space and an array initialEnergy[n] . The finalEnergy[i] of the i th particle is max(initialEnergy[i] - barrier, 0) . The goal is to find the maximum possible integer value of the barrier such that the sum of final energies of the particles is greater than or equal to a given threshold th . Example n = 5 , initialEnergy = [4, 8, 7, 1, 2] , th = 9 . Testing barrier values 0 through 4: barrier initialEnergy - barrier sum of to test final energies 0 4 8 7 1 2 22 1 3 7 6 0 1 17 2 2 6 5 -1 0 13 3 1 5 4 -2 -1 10 4 0 4 3 -3 -2 7 Negative values are not part of the sums, since each finalEnergy[i] is max(value, 0) . The maximum value of barrier for which the sum of final energies is greater than or equal to th is 3 . Input Format The program reads from standard input: The first line contains an integer n , the number of elements in initialEnergy . Each line i of the n subsequent lines (where 0 ≤ i < n ) contains an integer, initialEnergy[i] . The next li