Cuộc tìm kiếm của Aroma

Trong không gian hai chiều có vô số nút dữ liệu, đánh số từ $0$. Toạ độ của các nút được xác định như sau:

• Nút thứ $0$ có toạ độ $(x_0,y_0)$.
• Với $i>0$, nút thứ $i$ có toạ độ $(a_x·x_{i-1}+b_x,a_y·y_{i-1}+b_y)$, trong đó $(x_{i-1},y_{i-1})$ là toạ độ nút thứ $i-1$.

Ban đầu bạn đứng tại điểm $(x_s,y_s)$ và có tối đa $t$ giây. Mỗi giây bạn có thể di chuyển từ điểm $(x,y)$ sang một trong bốn điểm kề cạnh: $(x-1,y)$, $(x+1,y)$, $(x,y-1)$, $(x,y+1)$. Nếu tại vị trí đang đứng có một nút dữ liệu, bạn có thể thu thập nút đó (mất $0$ giây, mỗi nút chỉ thu thập được một lần).

Bạn không cần quay lại điểm xuất phát. Hãy tìm số nút dữ liệu nhiều nhất có thể thu thập được trong $t$ giây.

Dữ liệu vào

• Dòng đầu chứa sáu số nguyên $x_0,y_0,a_x,a_y,b_x,b_y$.
• Dòng thứ hai chứa ba số nguyên $x_s,y_s,t$.

Dữ liệu ra

In ra một số nguyên: số nút dữ liệu nhiều nhất có thể thu thập trong $t$ giây.

Ràng buộc

• $1\le x_0,y_0\le {10}^{16}$
• $2\le a_x,a_y\le 100$
• $0\le b_x,b_y\le {10}^{16}$
• $1\le x_s,y_s,t\le {10}^{16}$

Ví dụ