题目描述
现有三个正整数 A,B,CA,B,CA,B,C，请你找三个整数x,y,zx,y,zx,y,z满足x+y+z=nx+y+z=nx+y+z=n，且0≤x,y,z0\leq x,y,z0≤x,y,z，使得 ∣x∗A+y∗B+z∗C−W∣|x*A + y*B + z*C - W|∣x∗A+y∗B+z∗C−W∣ 最小。
为了简化题目，现在只要找到∣x∗A+y∗B+z∗C−W∣|x*A + y*B + z*C - W|∣x∗A+y∗B+z∗C−W∣的最小值。
输入
第一行一个正整数 T(1≤T≤103)T(1\leq T \leq 10^3)T(1≤T≤103)代表多组询问
接下来 TTT 行 每行五个正整数 A,B,C,n,WA,B,C,n,WA,B,C,n,W，(1≤A,B,C,n,W≤106)(1 \leq A,B,C,n,W\leq 10^6)(1≤A,B,C,n,W≤106)如题意所示
保证所有样例中 nnn 的和小于 10610^6106
输出
T 行每组询问输出一行，代表最小答案 样例输入 Copy
4
1 2 3 4 5
6 7 8 9 10
3 4 5 6 7
100 200 33 23 4
样例输出 Copy
0
44
11
755