Стабилизация кластеров чеков

Сеть супермаркетов группирует чеки по двум признакам: сумме покупки в десятках рублей и числу товаров. Для этого используется алгоритм k-средних с двумя кластерами.

Координаты чека равны \((x,y)\), где \(x\) — сумма покупки в десятках рублей, а \(y\) — число товаров. В начале заданы два центра кластеров \(C_1\) и \(C_2\). На каждой итерации каждому чеку назначается метка ближайшего центра по квадрату евклидова расстояния: \[ d^2((x,y),(a,b))=(x-a)^2+(y-b)^2. \] После назначения меток центр каждого непустого кластера заменяется средним арифметическим координат всех чеков этого кластера. Если кластер оказался пустым, его центр не изменяется.

Первой считается итерация, на которой метки назначаются по исходным центрам. Метки считаются стабилизировавшимися на первой итерации, на которой весь список меток совпал со списком меток предыдущей итерации. В конце входа задано число итераций запроса \(T\). Гарантируется, что метки стабилизируются не позднее итерации \(T\).

При равенстве расстояний чек получает метку кластера 1.

Формат ввода

В первой строке дано целое число \(n\) — число чеков.

В следующих \(n\) строках даны два целых числа \(x_i\) и \(y_i\) — сумма покупки в десятках рублей и число товаров в \(i\)-м чеке.

В следующих двух строках даны координаты исходных центров кластеров 1 и 2 соответственно.

В последней строке дано целое число \(T\) — параметр запроса, максимальное число рассматриваемых итераций.

Формат вывода

Выведите одно целое число — номер итерации, на которой метки чеков стабилизировались.

Дробная часть не возникает: требуется вывести целое число без округления.

Ограничения

\(1 \le n \le 4000\).

\(0 \le x_i \le 1000000\).

\(1 \le y_i \le 1000\).

Координаты каждого исходного центра удовлетворяют тем же ограничениям: от 0 до 1000000 для первой координаты и от 1 до 1000 для второй.

\(2 \le T \le 200\).

Гарантируется, что метки стабилизируются не позднее итерации \(T\).