Minimizing Colorfulness in a Crayon Selection

You are given n crayons. Each crayon has a color represented by three primary color components: red, green, and blue. The color of the i-th crayon is given by three integers \(R_i\), \(G_i\), and \(B_i\). The difference between two crayons \(i\) and \(j\) is defined as

[ \delta(i,j)=\max(|R_i-R_j|,,|G_i-G_j|,,|B_i-B_j|) ]

For any set of crayons, its colorfulness is defined as the maximum difference among any two crayons in the set. Your task is to choose k crayons such that the colorfulness of the chosen set is minimized. Equivalently, you need to find the smallest integer \(D\) such that there exists a subset of \(k\) crayons where for every pair \((i, j)\) in the subset,

[ \max(|R_i-R_j|,,|G_i-G_j|,,|B_i-B_j|) \le D. ]

Note that this condition is equivalent to requiring that all chosen crayons lie within an axis-aligned cube of side length \(D\) (in the Chebyshev norm).

inputFormat

The first line of input contains two integers \(n\) and \(k\) (\(1 \le k \le n\)). Each of the next \(n\) lines contains three integers \(R_i\), \(G_i\), and \(B_i\) representing the color components of the \(i\)-th crayon.

You may assume that the color components are integers.

outputFormat

Output a single integer: the minimum possible colorfulness (i.e. the smallest possible \(D\)) when choosing a subset of \(k\) crayons.

sample

3 2
0 0 0
0 0 1
1 1 1

1