CF1292B Aroma's Search

获得了新身体后，我们的偶像 Aroma White（或者应该被称为 Kaori Minamiya？）开始在 OS 空间中寻找她尘封的过去。 这个空间可以看作是一个二维平面，在其内部有着无限多的数据点，从 $0$ 开始标号，它们的坐标定义如下： - 第 $0$ 个点的坐标为 $(x_0, y_0)$。 - 对于 $i > 0$，第 $i$ 个点的坐标为 $(x_i, y_i) = (a_x \cdot x_{i-1} + b_x, a_y \cdot y_{i-1} + b_y)$。 初始时 Aroma 的位置为 $(x_s, y_s)$。她只能留在 OS 空间中最多 $t$ 秒，因为她还需要传送回真实世界。她不需要返回初始位置 $(x_s, y_s)$ 也能传送回家。 在 OS 空间中，Aroma 可以做如下操作： - 在点 $(x, y)$ 上时，Aroma 可以移动到这四个点之一：$(x-1, y), (x+1, y), (x, y-1), (x, y+1)$。这个操作需要耗费 $1$ 秒。 - 如果 Aroma 当前的位置上有数据点，她可以收集它。我们可以假定这个操作耗费 $0$ 秒。当然，每个数据点只能被收集一次。 Aroma 想要在传送回去之前，收集尽可能多的数据点。你能帮助她计算在 $t$ 秒内最多能收集的数据点的个数吗？

第一行输入六个整数 $x_0, y_0, a_x, a_y, b_x, b_y$，通过它们可以确定数据点的坐标。 第二行输入三个整数 $x_s, y_s, t$，表示 Aroma 的初始位置和可用的时间。 **数据范围：**$1 \le x_0, y_0, x_s, x_y, t \le {10}^{16}$，$2 \le a_x, a_y \le 100$，$0 \le b_x, b_y \le {10}^{16}$。

输出一个整数，表示 Aroma 最多能收集的数据点个数。 ### 样例解释 在每个样例中，前 $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$ 秒。 在第三个样例中，Aroma 无法收集任何数据点。她应该好好休息而不是像之前一样直接冲进 OS 空间。

In all three examples, the coordinates of the first $ 5 $ data nodes are $ (1, 1) $ , $ (3, 3) $ , $ (7, 9) $ , $ (15, 27) $ and $ (31, 81) $ (remember that nodes are numbered from $ 0 $ ). In the first example, the optimal route to collect $ 3 $ nodes is as follows: - Go to the coordinates $ (3, 3) $ and collect the $ 1 $ -st node. This takes $ |3 - 2| + |3 - 4| = 2 $ seconds. - Go to the coordinates $ (1, 1) $ and collect the $ 0 $ -th node. This takes $ |1 - 3| + |1 - 3| = 4 $ seconds. - Go to the coordinates $ (7, 9) $ and collect the $ 2 $ -nd node. This takes $ |7 - 1| + |9 - 1| = 14 $ seconds. In the second example, the optimal route to collect $ 2 $ nodes is as follows: - Collect the $ 3 $ -rd node. This requires no seconds. - Go to the coordinates $ (7, 9) $ and collect the $ 2 $ -th node. This takes $ |15 - 7| + |27 - 9| = 26 $ seconds. In the third example, Aroma can't collect any nodes. She should have taken proper rest instead of rushing into the OS space like that.