Fair cap: hints, no solution

A platform team shares a pool of compute quota among teams. Team i asks for requests[i] units. To keep things fair the platform sets one cap c for everybody: each team is granted the smaller of its request and c, so small requests are met in full and large ones are trimmed to the cap.

The total granted may not exceed the budget. Return the highest integer cap c, between 0 and the largest request, for which the total granted stays within the budget. If the budget covers every request in full, the answer is the largest request. A cap of 0 is always allowed.

Totals can exceed 32 bits, so use wider integers for the sum.

Examples

Input

requests = [4, 10, 6, 20], budget = 26

Output

8

Note

With cap 8 the grants are 4, 8, 6 and 8, totalling 26. With cap 9 they total 28, which is too much.

Input

requests = [3, 5, 2], budget = 100

Output

5

Note

With cap 1 three teams get 3 in total; with cap 2 they would need 6.

Constraints

• 1 <= requests.length <= 30000
• 0 <= requests[i] <= 1000000
• 0 <= budget <= 2000000000

Hint 1: a nudge

If you tried one particular cap, how would you find the total granted? And if that total is within budget, what does it say about smaller caps?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing