代价转移
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定正整数 a 和 b，你每次可以从下面三种操作中选择任意一种：

  • 将 a 加一：a \leftarrow a + 1，代价为 C_1；
  • 将 a 减一：a \leftarrow a - 1，代价为 C_2；
  • 将 a 乘二：a \leftarrow a \times 2，代价为 C_3。

计算将 a 变成 b 的最小代价。

输入描述:

第一行只有一个整数 t（1 \le t \le 10^4），表示测试数据组数。

接下来每行一组测试数据，包含五个整数 a,b,C_1,C_2,C_3 (1 \le a,b \le {10}^3,1\le C_1,C_2,C_3 \le {10}^3)。

输出描述:

对于每组测试数据，在一行中输出一个整数，表示将 a 变成 b 所需的最小总代价。
示例1

输入

复制 
4
4 6 1 1 2
3 10 2 1 3
8 3 1 1 2
3 3 1 1 1

输出

复制 
2
7
5
0

备注:

样例 1：a=4,b=6,C_1=C_2=1,C_3=2。最优做法是对 4 连续两次“加一”：4 \xrightarrow{+1} 5 \xrightarrow{+1} 6, 总代价 2\times C_1 = 2。
样例 2：a=3,b=10,C_1=2,C_2=1,C_3=3。最优做法是“加一”两次得到 5，再“乘二”得到 10： 3 \xrightarrow{+1} 4 \xrightarrow{+1} 5 \xrightarrow{\times2} 10, 总代价 2\times C_1 + 1\times C_3 = 2\cdot2 + 3 = 7。 
样例 3：a=8,b=3,C_1=C_2=1,C_3=2。最优做法是“减一” 5 次： 8 \xrightarrow{-1} 7 \xrightarrow{-1} 6 \xrightarrow{-1} 5 \xrightarrow{-1} 4 \xrightarrow{-1} 3, 总代价为 5 \times C_2 = 5。