Log Truncation

You are given a list of integers logs and an integer limit. Each element in logs[i] represents the size of logs generated by user i. limit represents the total size of logs you can store in your system.

Return the largest x such that if we truncate every log in logs to be at most size x, the sum of the remaining log sizes is at most limit. If no log needs to be truncated, return the largest log size.

Constraints

• 1 ≤ n ≤ 100,000 where n is the length of logs
• 1 ≤ limit < 2 ** 31

https://binarysearch.com/problems/Log-Truncation

Examples

Example 1

Input

• logs = [50, 20, 1000, 50, 400]
• limit = 300

Output

• answer = 90

Explanation

If we truncate logs to 90, then we get [50, 20, 90, 50, 90] and its sum is 300

Example 2

Input

• logs = [2, 3, 7]
• limit = 100

Output

• answer = 7

Explanation

No message needs to be truncated, so we return the max log size.

Solution