← 返回题目列表

Codeforces · 261/A

A. 马克西姆和折扣

中文机器翻译题面 查看原题

马克西姆周日总是去超市。今天超市有特别优惠的折扣系统。

有 m 种折扣。我们假设折扣从 1 到 m 进行索引。为了使用折扣号 i,顾客需要一个特殊的篮子,里面放着他购买的 qi 件商品。根据折扣制度的条款,除了购物车中的商品外,顾客还可以从超市免费获得最多两件商品。提供的“免费物品”的数量(0、1或2)由顾客选择。所选“免费商品”的唯一条件是:每件商品的价格不得比购物车中 qi 商品中最便宜的商品贵。

Maxim现在需要在商店购买n件物品。如果马克西姆能够很好地利用折扣系统,请计算他购买它们所需的最低金额。

请假设超市有足够的购物车来进行任何操作。 Maxim 可以多次使用相同的折扣。当然,Maxim 可以无折扣地购买商品。

输入

第一行包含整数 m (1 ≤ m ≤ 105) — 折扣类型的数量。第二行包含 m 个整数:q1, q2, ..., qm (1 ≤ qi ≤ 105)。

第三行包含整数 n (1 ≤ n ≤ 105) — Maxim 需要的项目数。第四行包含 n 个整数:a1, a2, ..., an (1 ≤ ai ≤ 104) — 商品的价格。

行中的数字由单个空格分隔。

输出

在一行中打印一个整数——问题的答案。

示例

输入 #1

1
2
4
50 50 100 100

输出 #1

200

输入 #2

2
2 3
5
50 50 50 50 50

输出 #2

150

输入 #3

1
1
7
1 1 1 1 1 1 1

输出 #3

3

注意

在第一个示例中,Maxim 需要购买两件价值 100 美元的商品,并获得两件价值 50 美元的免费商品的折扣。在这种情况下,Maxim 将支付 200 美元。

在第二个示例中,Maxim 的最佳策略是购买 3 件商品并使用折扣免费获得 2 件商品。在这种情况下,Maxim 将支付 150。