#221. 商人小雅米

商人小雅米往返于 A,B 两个城市之间进行贸易，两座城市都只有三种商品——金、银、铜。在 A 城市中三种商品每单位的价格分别为 $g_a,s_a,b_a$ 元，在 B 城市中三种商品每单位的价格分别为 $g_b,s_b,b_b$ 元,所有商品都只能一单元一单位进行购买。小雅米将带着 $S$ 元从 A 城市出发，往返于两座城市之间 $n$ 趟(从 A 走到 B 再走到 A 算作一趟），最后于 A 城市结束贸易。小雅米最多能携带 $k$ 单位的商品，请问他结束时最多能获得多少元。

第一行一个整数 $T(1\leq T\leq 10)$ 代表数据组数。

每组数据第一行三个数 $n,k,S (1\leq n \leq 10^9 ,1\leq k \leq 50, 1\leq S \leq 10^9)$，含义如描述所示。

第二行三个整数 $g_a,s_a,b_a (1\leq g_a,s_a,b_a\leq 200)$，含义如描述所示。

第三行三个整数 $g_b,s_b,b_b (1\leq g_b,s_b,b_b \leq 200)$，含义如描述所示。

对于每组测试数据输出一行一个整数，代表结束贸易时小雅米最多能有多少钱。

输入样例

2
100 50 1000
2 2 2
3 2 2
337 43 10
3 4 5
6 8 2

输出样例

6000
101064