B. Арома и её поиск
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
THE SxPLAY & KIVΛ - 漂流
KIVΛ & Nikki Simmons - Perspectives

С новым телом наш идол Арома Белая (или лучше было сказать Каори Минамийа?) начинает восстанавливать своё потерянное прошлое через OS-пространство.

Это пространство можно представить как 2D плоскость, с бесконечным количеством устройств с данными, пронумерованных с $$$0$$$. Координаты устройств можно описать следующим образом:

  • Координаты $$$0$$$-го устройства равны $$$(x_0, y_0)$$$
  • Для $$$i > 0$$$, координаты $$$i$$$-го устройства равны $$$(a_x \cdot x_{i-1} + b_x, a_y \cdot y_{i-1} + b_y)$$$

Изначально Арома расположена в точке $$$(x_s, y_s)$$$. Она может находиться в OS-пространстве не более $$$t$$$ секунд, после этого ей придётся вернуться в реальный мир. Чтобы вернутся в реальный мир не требуется возвращаться в изначальную точку $$$(x_s, y_s)$$$.

Внутри OS-пространства Арома может делать следующие действия:

  • Из точки $$$(x, y)$$$ Арома может перейти в одну из следующих точек $$$(x-1, y)$$$, $$$(x+1, y)$$$, $$$(x, y-1)$$$ или $$$(x, y+1)$$$. Это действие занимает $$$1$$$ секунду.
  • Если Арома стоит в точке с устройством, то она может его собрать. Можно считать, что это действие занимает $$$0$$$ секунд. Разумеется, каждое устройство можно собрать не более одного раза.

Арома хочет собрать как можно больше данных перед тем как вернётся назад. Помогите ей определить максимальное количество устройств с данными, которые она сможет собрать за $$$t$$$ секунд.

Входные данные

Первая строка содержит целые числа $$$x_0$$$, $$$y_0$$$, $$$a_x$$$, $$$a_y$$$, $$$b_x$$$, $$$b_y$$$ ($$$1 \leq x_0, y_0 \leq 10^{16}$$$, $$$2 \leq a_x, a_y \leq 100$$$, $$$0 \leq b_x, b_y \leq 10^{16}$$$), которые задают координаты устройств с данными.

Вторая строка содержит целые числа $$$x_s$$$, $$$y_s$$$, $$$t$$$ ($$$1 \leq x_s, y_s, t \leq 10^{16}$$$), изначальные координаты Аромы и доступное время.

Выходные данные

Выведите одно целое число — максимальное количество устройств с данными которые Арома сможет собрать за $$$t$$$ секунд.

Примеры
Входные данные
1 1 2 3 1 0
2 4 20
Выходные данные
3
Входные данные
1 1 2 3 1 0
15 27 26
Выходные данные
2
Входные данные
1 1 2 3 1 0
2 2 1
Выходные данные
0
Примечание

Во всех трёх примерах, координаты первых $$$5$$$ устройств равны $$$(1, 1)$$$, $$$(3, 3)$$$, $$$(7, 9)$$$, $$$(15, 27)$$$ и $$$(31, 81)$$$ (напомним, что устройства пронумерованы начиная с $$$0$$$).

В первом примере оптимальный маршрут чтобы собрать $$$3$$$ вершины выглядит следующим образом:

  • Перейти в точку $$$(3, 3)$$$ и собрать $$$1$$$-е устройство. Это занимает $$$|3 - 2| + |3 - 4| = 2$$$ секунд.
  • Перейти в точку $$$(1, 1)$$$ и собрать $$$0$$$-е устройство. Это занимает $$$|1 - 3| + |1 - 3| = 4$$$ секунд.
  • Перейти в точку $$$(7, 9)$$$ и собрать $$$2$$$-е устройство. Это занимает $$$|7 - 1| + |9 - 1| = 14$$$ секунд.

Во втором примере оптимальный маршрут чтобы собрать $$$2$$$ вершины выглядит следующим образом:

  • Собрать $$$3$$$-е устройство. Это занимает ноль секунд.
  • Перейти в точку $$$(7, 9)$$$ и собрать $$$2$$$-е устройство. Это занимает $$$|15 - 7| + |27 - 9| = 26$$$ секунд.

В третьем примере Арома не может собрать ни одного устройства. Пожалуй стоило отдохнуть, а не рваться в OS-пространство без подготовки.