Minimize Maximum Weight Difference in Groups

You are given an array of integers representing the weights of coins, and a positive integer K representing the number of groups to form. Your task is to partition the sorted list of weights into at most K contiguous groups. In each group, compute the difference between the maximum and minimum weight. The goal is to minimize the largest of these differences across all groups.

Formally, let \(w_1, w_2, \dots, w_n\) be the weights (after sorting in non-decreasing order), and let the partition be formed by breaking the array into segments. For each segment, define the difference \(D = \max(\text{segment}) - \min(\text{segment})\). You need to choose the partition such that \( \max_{\text{segment}} D\) is minimized. Output this minimum possible largest difference.

Note: It is always optimal to partition the sorted array into contiguous segments.

inputFormat

The first line contains two space-separated integers \(n\) and \(K\), where \(n\) is the number of coins and \(K\) is the required number of groups. The second line contains \(n\) space-separated integers, representing the weights of the coins.

outputFormat

Output a single integer, the minimized largest difference between the weights within any group after partitioning optimally.

6 3
8 1 6 4 2 10

2