1011: 买年货

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:61 Solved:4

Description

新年到了,CJ开始着手置办年货。新春佳节之时,各大商场都会推出各种各样的优惠活动。今年商场的优惠活动是这样的:

       商场提供了M种类型的优惠,我们将这些优惠类型从1到i编号。如果要使用第i种优惠,那么商场会提供给顾客一个正好能装qi(1 ≤ qi 104)个商品的篮子,顾客必须在这个篮子里装恰好qi件商品(不能多装也不能少装),在顾客装完之后,顾客可以免费挑选两件商品,不过这是有前提的:顾客挑选的两件商品的价格必须要小于等于篮子里最便宜的物品价格。所有类型的优惠可以使用无限次,当然也可以不使用优惠,单独购买一个商品。

       CJ列了一个购物清单,清单上有N(1 ≤ N ≤ 105)件商品,现在告诉你每件商品的价格ai(1 ≤ ai 104)以及M(1 ≤ M 105)种优惠的类型。现在让你求CJ购买这N件商品所需要的最小花费。

Input

输入共4行:

第一行为1个正整数M,代表有M种类型的优惠

       接下来M个正整数,以空格分隔,代表qi,描述第i种优惠类型

       第三行为一个正整数N,代表CJ的购物清单上有N件商品

       接下来N个正整数,以空格分隔,代表ai,描述第i件商品的价格

Output

输出只有一行,表示CJ购买这N件商品所需要的最小花费。 

Sample Input Copy

1
2
4
50 50 100 100

Sample Output Copy

200

HINT

【样例输入】

2

2 3

5

50 50 50 50 50

【样例输出】

150



【样例解释】

       对于第一个样例,CJ使用唯一的折扣类型,购买3号、4号商品,同时附赠1号、2号商品。所以最小花费是:100 + 100 = 200。

 

对于第二个样例,CJ使用1号类型的折扣1次,购买任意两个商品(价值50),同时赠送两个商品(价值50),此时他已经购买了4件商品。最后还剩1件商品(价值50),由于没有对应的折扣类型,只能不使用折扣单买,所以最小花费是:50 + 50 +50 =150

 

【数据范围】

       对于100%的数据 1 ai ,qi104

 

       对于10%的数据,M = 0

对于20%的数据,M = 1

对于40%的数据,1 ≤ N,M ≤ 5

对于70%的数据,1 ≤ N,M ≤ 1000

对于100%的数据,1 ≤ N,M ≤ 100000