Minimum Weight Difference Between Packages

You are given n items with specified weights and k packages. Your task is to distribute the items into the packages such that the difference between the heaviest and the lightest package is minimized.

Let \(W_i\) denote the total weight of the \(i^{th}\) package. We want to minimize the difference \(\Delta = \max\{W_i\} - \min\{W_i\}\). A greedy strategy that sorts the items in descending order and assigns each item to the package with the smallest current total may lead to a near-optimal solution.

Note: It is guaranteed that a solution exists for all valid inputs.

inputFormat

The input is given via standard input (stdin) in the following format:

n k
w1 w2 ... wn

Where:

• n is the number of items.
• k is the number of packages.
• w1, w2, ..., wn are the weights of the items.

outputFormat

Output a single integer, which is the minimum possible difference between the maximum and minimum total weight of the packages, computed as:

\(\Delta = \max\{W_i\} - \min\{W_i\}\)

The output should be written to standard output (stdout).

## sample

5 2
8 1 7 3 9

2