Problem : 316 - Point group

Problem Statistics

Solved Member: 35　　Submission: 102　　User Tried: 37

Statement:

在一場不幸的意外中，你變成了魔法少女！從此以後戰鬥與守護世界和平就變成你的責任了。

然而在某次的戰鬥中，你陷入了苦戰。為了避免你的頭被敵人吃掉，你在天空中布置了魔法陣，準備與敵人決一死戰。

你在天空中的許多位置布置了 n 個魔法陣，以三維的座標表示他的位置。依據你的經驗，你必須將這些魔法陣分成恰好 k 個時間點施放。

任意位於 (x1,y1,z1) 與 (x2,y2,z2) 的魔法陣若在不同時間點施放會對敵人形成單次：
max(|x1-x2|, |y1-y2|, |z1-z2|) 的損傷。

你現在已經布置好魔法陣的位置了，現在該是計算該何時施放哪個魔法陣的時候了！由於你現在遇到的敵人回血非常快，你希望單次造成最小損傷越大越好。

Input:Output:

第一行有兩個數字 n,k ，代表魔法陣個數與你要分幾個時間點施放。
接下來 n 行，每行有三個數字 x,y,z ，代表第 i 個魔法陣的座標。

2 ≤ k ≤ n ≤ 2000
0 ≤ x,y,z ≤ 2000000000

請輸出一個數字，代表單次最小的損傷最大能多大。

Sample Input:Sample Output:

3 2
1 0 2
2 1 3
3 2 1

HINT:

範例中其中一種可能的解釋：

時間 1 施放魔法陣 1,2
時間 2 施放魔法陣 3

魔法陣 1,3 施放時間不同，造成損害 2
魔法陣 2,3 造成損害 2
最小的損害為 2

Source:

TOI 2013 1模

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	131072kb
1-1	1000ms	131072kb	20
1-2	1000ms	131072kb
2-1	1000ms	131072kb	20
2-2	1000ms	131072kb
3-1	1000ms	131072kb	20
3-2	1000ms	131072kb
4-1	5000ms	131072kb	20
4-2	5000ms	131072kb
5-1	5000ms	131072kb	20
5-2	5000ms	131072kb