1209:班长请客

时间限制: 3 S | 内存限制: 65536 KB
Accept: 57 | Submit: 131
[提交] [状态] [讨论版]
描述

有一个班的同学参加纪念五四运动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

HINT

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

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

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

来源
第七届编程大赛