Find the Smallest Divisor Given a Threshold

Binary Search
Binary Search On Answer

Given an integer array nums and an integer threshold, find the smallest positive integer d such that the sum of ceil(nums[i] / d) is ≤ threshold.

Examples

Example 1

Input

nums

1

2

5

9

threshold6

Output

5

Constraints

1 ≤ nums.length ≤ 5 * 10⁴
1 ≤ nums[i] ≤ 10⁶
nums.length ≤ threshold ≤ 10⁶

Stuck? Hint 1

Same shape as Koko — feasibility at d is sum of ceiled divisions ≤ threshold.

Input

1

2

5

9

threshold6

Expected Output

Ctrl / ⌘ + Enter

Find the Smallest Divisor Given a Threshold

Binary Search
Binary Search On Answer

Given an integer array nums and an integer threshold, find the smallest positive integer d such that the sum of ceil(nums[i] / d) is ≤ threshold.

Examples

Example 1

Input

nums

1

2

5

9

threshold6

Output

5

Constraints

1 ≤ nums.length ≤ 5 * 10⁴
1 ≤ nums[i] ≤ 10⁶
nums.length ≤ threshold ≤ 10⁶

Stuck? Hint 1

Same shape as Koko — feasibility at d is sum of ceiled divisions ≤ threshold.

Input

1

2

5

9

threshold6

Expected Output

Ctrl / ⌘ + Enter