#P17967. Four Kubic Theorem 2

Four Kubic Theorem 2

Four Kubic Theorem 2

给定一个质数 pp、整数 mm,以及四个整数 a1,a2,a3,a4a_1,a_2,a_3,a_4 和四个整数 b1,b2,b3,b4b_1,b_2,b_3,b_4。

选择四个非负整数 x1,x2,x3,x4x_1,x_2,x_3,x_4,使

a1x1+a2x2+a3x3+a4x4≡m(modp).a_1x_1+a_2x_2+a_3x_3+a_4x_4\equiv m\pmod p.

求 b1x1+b2x2+b3x3+b4x4b_1x_1+b_2x_2+b_3x_3+b_4x_4 的最小值。

输入格式

第一行是测试用例数 TT,1≤T≤1041\le T\le10^4。每组数据包含三行:

  • 第一行两个整数 p,mp,m;
  • 第二行四个整数 a1,a2,a3,a4a_1,a_2,a_3,a_4;
  • 第三行四个整数 b1,b2,b3,b4b_1,b_2,b_3,b_4。

pp 是质数,2≤p≤1.01×1092\le p\le1.01\times10^9,0≤m<p0\le m<p,1≤ai<p1\le a_i<p,1≤bi≤1091\le b_i\le10^9。

所有测试用例的 ⌈p⌉\lceil\sqrt p\rceil 之和不超过 2172^{17}。

输出格式

每组数据输出一行一个整数,表示目标表达式的最小值。

样例输入

3
101 99
1 2 3 4
5 6 7 8
998244353 114514
1919 811 123 777
1000000000 1000000000 1000000000 1000000000
1000000007 767336601
142205992 920557330 725753607 763861942
1 1 1 1

样例输出

199
76000000000
187