商人小雅米往返于 A,B 两个城市之间进行贸易，两座城市都只有三种商品——金、银、铜。在 A 城市中三种商品每单位的价格分别为 ga,sa,bag_a,s_a,b_aga,sa,ba 元，在 B 城市中三种商品每单位的价格分别为 gb,sb,bbg_b,s_b,b_bgb,sb,bb 元,所有商品都只能一单元一单位进行购买。小雅米将带着 SSS 元从 A 城市出发，往返于两座城市之间 nnn 趟(从 A 走到 B 再走到 A 算作一趟），最后于 A 城市结束贸易。小雅米最多能携带 kkk 单位的商品，请问他结束时最多能获得多少元。
第一行一个整数 T(1≤T≤10)T(1\leq T\leq 10)T(1≤T≤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)n,k,S(1≤n≤109,1≤k≤50,1≤S≤109)，含义如描述所示。
第二行三个整数 ga,sa,ba(1≤ga,sa,ba≤200)g_a,s_a,b_a (1\leq g_a,s_a,b_a\leq 200)ga,sa,ba(1≤ga,sa,ba≤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)gb,sb,bb(1≤gb,sb,bb≤200)，含义如描述所示。
对于每组测试数据输出一行一个整数，代表结束贸易时小雅米最多能有多少钱。
2 100 50 1000 2 2 2 3 2 2 337 43 10 3 4 5 6 8 2
6000 101064
