Matrix

有一个二维平面，给定 $length[1], length[2], length[3], length[4]$，画出 4 个正方形区域。 第 $i$ 个区域为 ${(x, y)\ |\ |x| <= length[i], |y| <= length[i]}$。 对于一个整点 $(x, y)$ 其权值为 $(|x|+|y|) * cnt$，其中 $cnt$ 为覆盖该点的区域个数。（点在区域边界上或者在区域内，都称为被区域覆盖）。 现在需要在至少被一个区域覆盖的整点点集中，选出 $k$ 个两两不同的点，使得总权值和最小。 输出最小的权值总和。

第一行一个整数 $T(T \le 100)$ 表示 $T$ 组测试数据。 每组数据有 5 个数字，分别表示 $length[1], length[2], length[3], length[4], k$。满足 $1 \le length[1] < length[2] < length[3] < length[4] \le 10^9, 0 \le k \le 10^{10}$。 数据保证一定能选出 $k$ 个点。

对每组数据输出一行，表示答案。