有了新的身体,我们的偶像 Aroma White(或者我们应该叫她南宫香织?)开始通过操作系统空间揭开她失去的过去。
该空间可以被认为是一个 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)$$$
最初 Aroma 位于 $$$(x_s, y_s)$$$ 点。她最多可以在操作系统空间停留 $$$t$$$ 秒,因为在这段时间之后她必须回到现实世界。她不需要返回入口点 $$$(x_s, y_s)$$$ 来扭曲回家。
在操作系统空间内,Aroma 可以执行以下操作:
- 从点 $$$(x, y)$$$ 开始,香气可以移动到以下点之一:$$$(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$$$ ($$$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}$$$) – 初始 Aroma 的坐标和可用时间。
输出
打印单个整数 - Aroma 在 $$$t$$$ 秒内可以收集的最大数据节点数。
示例
输入 #1
1 1 2 3 1 0 2 4 20
输出 #1
3
输入 #2
1 1 2 3 1 0 15 27 26
输出 #2
2
输入 #3
1 1 2 3 1 0 2 2 1
输出 #3
0
注意
在所有三个示例中,前 $$$5$$$ 数据节点的坐标为 $$$(1, 1)$$$、$$$(3, 3)$$$、$$$(7, 9)$$$、$$$(15, 27)$$$ 和 $$$(31, 81)$$$(请记住,节点从 $$$0$$$ 开始编号)。
在第一个示例中,收集 $$$3$$$ 节点的最佳路线如下:
- 前往坐标 $$$(3, 3)$$$ 并收集 $$$1$$$-st 节点。这需要 $$$|3 - 2| + |3 - 4| = 2$$$ 秒。
- 前往坐标 $$$(1, 1)$$$ 并收集第 $$$0$$$ 个节点。这需要 $$$|1 - 3| + |1 - 3| = 4$$$ 秒。
- 前往坐标 $$$(7, 9)$$$ 并收集 $$$2$$$-nd 节点。这需要 $$$|7 - 1| + |9 - 1| = 14$$$ 秒。
在第二个示例中,收集 $$$2$$$ 节点的最佳路线如下:
- 收集 $$$3$$$-rd 节点。这不需要几秒钟。
- 前往坐标 $$$(7, 9)$$$ 并收集第 $$$2$$$ 个节点。这需要 $$$|15 - 7| + |27 - 9| = 26$$$ 秒。
在第三个示例中,Aroma 无法收集任何节点。她应该好好休息一下,而不是像这样冲进操作系统领域。