Four Kubic Theorem 2
给定一个质数 p、整数 m,以及四个整数 a1,a2,a3,a4 和四个整数 b1,b2,b3,b4。
选择四个非负整数 x1,x2,x3,x4,使
a1x1+a2x2+a3x3+a4x4≡m(modp).
求 b1x1+b2x2+b3x3+b4x4 的最小值。
输入格式
第一行是测试用例数 T,1≤T≤104。每组数据包含三行:
- 第一行两个整数 p,m;
- 第二行四个整数 a1,a2,a3,a4;
- 第三行四个整数 b1,b2,b3,b4。
p 是质数,2≤p≤1.01×109,0≤m<p,1≤ai<p,1≤bi≤109。
所有测试用例的 ⌈p⌉ 之和不超过 217。
输出格式
每组数据输出一行一个整数,表示目标表达式的最小值。
样例输入
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