У вас есть \(n\) различных точек \((x_1, y_1),\ldots,(x_n,y_n)\) на плоскости и неотрицательное целое число \(k\). Каждая точка представляет собой микроскопический стальной шарик, а \(k\) — это его сила притяжения, когда он заряжен. Сила притяжения одинакова для всех шариков.
За одну операцию вы можете выбрать шарик \(i\) и зарядить его. После этого все шарики на манхеттенском расстоянии не более \(k\) от шарика \(i\) перемещаются в позицию шарика \(i\). После этой операции несколько различных шариков могут оказаться в одной точке.
Более формально, для всех шариков \(j\) таких, что \(|x_i - x_j| + |y_i - y_j| \le k\), мы присваиваем \(x_j:=x_i\) и \(y_j:=y_i\).
Пример операции. После зарядки шарика в центре два других шарика перемещаются в его позицию. На правой картинке красная точка в центре — это общее положение этих шариков после операции. Ваша задача — найти минимальное количество операций, нужное для того, чтобы переместить все шарики в одну точку, или сообщить, что это сделать невозможно.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — минимальное количество операций, нужное для того, чтобы переместить все шарики в одну точку, или \(-1\), если это сделать невозможно.
Примечание
В первом наборе входных данных три шарика находятся в \((0, 0)\), \((3, 3)\), и \((1, 1)\) и сила притяжения равна \(2\). Можно переместить два шарика в одну точку за одну операцию, но невозможно переместить все три шарика в одну точку за любое количество операций.
Во втором наборе входных данных три шарика находятся шарика в \((6, 7)\), \((8, 8)\), и \((6, 9)\) и сила притяжения равна \(3\). Если мы зарядим любой шарик, другие два переместятся в его позицию, поэтому нам достаточно одной операции.
В третьем наборе входных данных четыре шарика находятся в \((0, 0)\), \((0, 1)\), \((0, 2)\) и \((0, 3)\) и сила притяжения равна \(1\). Можно показать, что невозможно переместить все шарики в одну и ту же точку какой-то последовательностью операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 2
0 0
3 3
1 1
3 3
6 7
8 8
6 9
4 1
0 0
0 1
0 2
0 3
|
-1
1
-1
|