U137933.pangz 老湿的体重管理

pangz 老湿又站上了那台神奇的体重秤。体重秤只显示一个 $0$ 到 $M-1$ 之间的整数，当前显示为 $S$。

为了让体重秤显示目标数字 $T$，pangz 老湿可以反复选择以下三种方案。若操作前显示的数字为 $x$，操作后的数字和本次消耗的体力分别为：

• 加餐：数字变为 $(x+A)\bmod M$，消耗 $W_A$ 点体力；
• 锻炼：数字变为 $(x-B)\bmod M$，消耗 $W_B$ 点体力；
• 神奇加倍：数字变为 $(x\times C)\bmod M$，消耗 $W_C$ 点体力。

其中，取模后的结果总是表示为 $0$ 到 $M-1$ 之间的整数。例如，$(-1)\bmod 5$ 在本题中表示 $4$。三种方案均可使用任意多次。

请你求出让体重秤从 $S$ 变为 $T$ 所需的最少体力；如果无法到达 $T$，输出 $-1$。

第一行输入三个整数 $M,S,T$（$2\le M\le 3\times 10^5$，$0\le S,T<M$），分别表示模数、起始数字和目标数字。

第二行输入三个整数 $A,B,C$（$0\le A,B,C<M$），分别表示三种操作的参数。

第三行输入三个整数 $W_A,W_B,W_C$（$1\le W_A,W_B,W_C\le 10^9$），分别表示三种操作消耗的体力。

输出一个整数，表示从 $S$ 到达 $T$ 所需的最少体力；如果无法到达，输出 $-1$。

提示

样例 $1$ 中，可以先选择一次加餐，使数字从 $1$ 变为 $4$，再选择一次神奇加倍，使数字从 $4$ 变为 $8$，总共消耗 $2+3=5$ 点体力。

样例 $2$ 中，虽然一次神奇加倍就能到达目标，但连续三次加餐消耗的体力更少。

答案可能超过 $32$ 位有符号整数的表示范围。