Chocolate Distribution

medium

1. Given an array A[] of positive integers of size N, where each value represents the number of chocolates in a packet. Each packet can have a variable number of chocolates. There are M students, the task is to distribute chocolate packets among M students such that :
2. Each student gets exactly one packet.
3. The difference between maximum number of chocolates given to a student and minimum number of chocolates given to a student is minimum.

Input Format

Input is managed for you

Output Format

Output is managed for you

Constraints

 1 &lt;= N &lt;= 10^5
1 &lt;= Ai &lt;= 10^9
1 &lt;= M &lt;= N

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input

8
3 4 1 9 56 7 9 12
5

Output

Find The Smallest Divisor Given A Threshold

Capacity To Ship Packages Within D Days