1209:班长请客

有一个班的同学参加纪念五四运动100周年活动，回宿舍的时候已经完美地错过了食堂的饭点，于是班长决定通过饿了么app点餐请班上所有同学吃饭，每人一份套餐。

假设班上有n名同学，网上有m家店铺可以提供送餐服务。每家店铺由于规模大小不同，最多可提供的套餐数量也有所不同，分别为a1、a2、...、am份。每家店铺为套餐定的单价也有所不同，有的店铺卖得贵，有的店铺卖得便宜，分别为每份c1、c2、...、cm元。班长可以任意地从其中的某些店铺点任意份套餐（但在某家店铺点的套餐数量，不能超过该家店铺最多可提供的套餐数量）。每家店铺在提供送餐服务时，除了按份数和单价的乘积收取套餐费用外，还要收取一笔送餐费用t（固定值，不管送多少份都一样，但是如果从多家店铺订餐，则需要收取多笔送餐费）。

请帮班长想一种最省钱的方案。

一个正整数T，表示案例的数量。

每组案例先是两个正整数n和m，表示同学的数量和店铺的数量。然后是m个正整数a1、a2、...、am，表示每家店铺能提供的套餐数量。然后是m个正整数c1、c2、...、cm，表示每家店铺一份套餐的价格。最后是一个正整数t，表示每一家店铺订餐的送餐费。（n<=10000, m<=10, a1...am<=10000, c1...cm<=10000）

针对每组案例，输出一个正整数，表示最省钱方案需要花费的金额。

每组案例输出完都要换行。

2

2 3

3 5 1

1 3 5

1

2 3

3 5 1

5 3 1

5

3

11

饿了么APP没有赞助本次竞赛

第一组案例，最省钱的方法是在第1家店订2份套餐，花2元，加上送餐费1元，一共花费3元。

第二组案例，最省钱的方法是在第2家店订2份套餐，花6元，加上送餐费5元，一共花费11元。注意，这组案例中，如果第2家和第3家各订一份，花4元，加上送餐费要2家店各5元，一共花费14元，不是最省钱的方法。