You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 Z 有 $N$ 支彩笔，每支笔都有 $R_i,G_i,B_i$ 三个属性值。

第 $i$ 支笔和第 $j$ 支笔的 Difference 值等于 $\max( \vert R_i-R_j\vert,\vert G_i-G_j\vert,\vert B_i-B_j\vert)$，而 Colorfulness 值等于所选笔中 Difference 值的最大值。

小 Z 需要从中选出 $K$ 支笔使得 Colorfulness 值尽可能的小，输出最小的 Colorfulness 值。

输入格式

从 rgb.in 文件读入数据。

输入第一行，包含两个正整数 $N,K$。

接下来的 $N$ 行中第 $i$ 行包含三个整数 $R_i,G_i,B_i$。

输出格式

输出到 rgb.out 文件。

输出一行一个整数，表示最小的 Colorfulness 值。

样例

2 2
1 3 2
2 6 4

3

5 3
6 6 4
6 2 7
3 1 3
4 1 5
6 2 6

2

样例3

此样例满足 $0\le R_i,G_i,B_i\le50$ 数据范围限制。

点击链接 ex_rgb3.in 和 ex_rgb3.out 下载大样例 3 的输入数据和输出数据。

样例4

此样例满足 $0\le R_i,G_i,B_i\le 255$ 数据范围限制。

点击链接 ex_rgb4.in 和 ex_rgb4.out 下载大样例 4 的输入数据和输出数据。

说明/提示

$50\%$ 的数据 $0\le R_i,G_i,B_i\le20$。

$80\%$ 的数据 $0\le R_i,G_i,B_i\le50$。

$100\%$ 的数据 $0\le R_i,G_i,B_i\le255,2\le K \le N \le 10^5$。