seuOJ221 - 商人小雅米

题目描述

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

输入格式

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

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

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

第三行三个整数 gb,sb,bb(1≤gb,sb,bb≤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