495. EKO — Cutting Logs (Maximum Sawblade Height)

Given the heights of trees and a required amount of wood M, set a sawblade at height H so that everything above H is cut; the wood collected is the sum over trees of (height - H) for trees taller than H. Return the maximum integer H such that at least M units of wood are collected. Input: '[trees], M'.

Input: '[trees], M'.

Output: Integer — the maximum sawblade height.

Examples

Input: [20,15,10,17], 7
Output: 15
Explanation: At H=15 wood = 5+0+0+2 = 7.

Input: [4,42,40,26,46], 20
Output: 36
Explanation: Maximum feasible height.

Input: [5], 3
Output: 2
Explanation: Cut 3 from a height-5 tree.

Constraints

• 1<=n<=10^6
• 1<=height<=10^9
• M>=1

Asked by