# Object Clustering

Time Limit: 2000MS

Memory Limit: 131072K

## Description

We have *N *(*N* ≤ 10000) objects, and wish to classify them into several groups by judgement of their resemblance. To simply the model, each object has 2 indexes *a* and *b* (*a*, *b* ≤ 500). The resemblance of object *i* and object *j* is defined by *d*_{ij} = |*a*_{i }-* a*_{j}| + |*b*_{i }-* b*_{j}|, and then we say *i* is *d*_{ij} resemble to *j*. Now we want to find the minimum value of *X*, so that we can classify the *N* objects into *K* (*K *< N) groups, and in each group, one object is at most *X* resemble to another object in the same group, i.e, for every object *i*, if *i* is not the only member of the group, then there exists one object *j* (i ≠ j) in the same group that satisfies *d*_{ij} ≤ *X*

## Output

A single line contains the minimum X.