{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eWe have \u003ci\u003eN \u003c/i\u003e(\u003ci\u003eN\u003c/i\u003e ≤ 10000) objects, and wish to classify them into several groups by judgement of their resemblance. To simply the model, each object has 2 indexes \u003ci\u003ea\u003c/i\u003e and \u003ci\u003eb\u003c/i\u003e (\u003ci\u003ea\u003c/i\u003e, \u003ci\u003eb\u003c/i\u003e ≤ 500). The resemblance of object \u003ci\u003ei\u003c/i\u003e and object \u003ci\u003ej\u003c/i\u003e is defined by \u003ci\u003ed\u003csub\u003eij\u003c/sub\u003e\u003c/i\u003e \u003d |\u003ci\u003ea\u003csub\u003ei \u003c/sub\u003e\u003c/i\u003e-\u003ci\u003e a\u003csub\u003ej\u003c/sub\u003e\u003c/i\u003e| + |\u003ci\u003eb\u003csub\u003ei \u003c/sub\u003e\u003c/i\u003e-\u003ci\u003e b\u003csub\u003ej\u003c/sub\u003e\u003c/i\u003e|, and then we say \u003ci\u003ei\u003c/i\u003e is \u003ci\u003ed\u003csub\u003eij\u003c/sub\u003e\u003c/i\u003e resemble to \u003ci\u003ej\u003c/i\u003e. Now we want to find the minimum value of \u003ci\u003eX\u003c/i\u003e, so that we can classify the \u003ci\u003eN\u003c/i\u003e objects into \u003ci\u003eK\u003c/i\u003e (\u003ci\u003eK \u003c/i\u003e\u0026lt; N) groups, and in each group, one object is at most \u003ci\u003eX\u003c/i\u003e resemble to another object in the same group, i.e, for every object \u003ci\u003ei\u003c/i\u003e, if \u003ci\u003ei\u003c/i\u003e is not the only member of the group, then there exists one object \u003ci\u003ej\u003c/i\u003e (i ≠ j) in the same group that satisfies \u003ci\u003ed\u003csub\u003eij\u003c/sub\u003e\u003c/i\u003e ≤ \u003ci\u003eX\u003c/i\u003e\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains two integers \u003ci\u003eN\u003c/i\u003e and \u003ci\u003eK\u003c/i\u003e. The following \u003ci\u003eN\u003c/i\u003e lines each contain two integers \u003ci\u003ea\u003c/i\u003e and \u003ci\u003eb\u003c/i\u003e, which describe a object. \u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eA single line contains the minimum X. \u003c/p\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e6 2\r\n1 2\r\n2 3\r\n2 2\r\n3 4\r\n4 3\r\n3 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}