思维261A · Maxim and Discounts
Maxim 每个星期天都会去超市。今天超市有一个折扣系统的特别优惠。
有 m 种折扣。我们假设折扣从 1 到 m 编号。要使用第 i 种折扣，顾客拿一个特殊的篮子，里面恰好放他购买的 qi 件商品。根据折扣系统的条款，除了购物车中的商品外，顾客最多可以从超市免费获得两件商品。“免费商品”的数量（0、1 或 2）由顾客选择。对所选“免费商品”的唯一条件如下：它们中的每一件都不能比购物车中 qi 件商品里最便宜的那件更贵。
Maxim 现在需要在商店购买 n 件商品。计算 Maxim 最优使用折扣系统购买它们所需的最小金额。
请假设超市有足够的购物车用于任何操作。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
2
4
50 50 100 100
输出
200
输入
2
2 3
5
50 50 50 50 50
输出
150
输入
1
1
7
1 1 1 1 1 1 1
输出
3
提示
在第一个样例中，Maxim 需要购买两件价格为 100 的商品，并获得两件价格为 50 的免费商品的折扣。在这种情况下，Maxim 将支付 200。
在第二个样例中，Maxim 的最佳策略是购买 3 件商品并使用该折扣免费获得 2 件商品。在这种情况下，Maxim 将支付 150。
提示
难度 1400 · greedy, sortings
构造1158A · The Party and Sweets
n 个男孩和 m 个女孩来参加聚会。每个男孩送给每个女孩一些整数数量的糖果（可能为零）。所有男孩用从 1 到 n 的整数编号，所有女孩用从 1 到 m 的整数编号。对于所有 1 ≤ i ≤ n，第 i 个男孩送给某个女孩的最少糖果数等于 b_i；对于所有 1 ≤ j ≤ m，第 j 个女孩从某个男孩那里收到的最多糖果数等于 g_j。
更形式化地说，设 a_{i,j} 为第 i 个男孩给第 j 个女孩的糖果数。那么 b_i 恰好等于值 a_{i,1}, a_{i,2}, …, a_{i,m} 中的最小值，而 g_j 恰好等于值 a_{1,j}, a_{2,j}, …, a_{n,j} 中的最大值。
你关心男孩们可能送出的最少糖果总数，因此你需要对于所有满足 1 ≤ i ≤ n 且 1 ≤ j ≤ m 的 (i,j)，最小化 a_{i,j} 的和。给定数字 b_1, …, b_n 和 g_1, …, g_m，求出这个数。
输入 / 输出 / 样例（含数据范围）· 不写代码可以跳过
输入
第一行包含两个用空格分隔的整数 n 和 m——分别是男孩和女孩的数量（2 ≤ n, m ≤ 100000）。第二行包含 n 个用空格分隔的整数 b_1, …, b_n——b_i 等于第 i 个男孩送给某个女孩的最少糖果数（0 ≤ b_i ≤ 10^8）。第三行包含 m 个用空格分隔的整数 g_1, …, g_m——g_j 等于第 j 个女孩从某个男孩那里收到的最多糖果数（0 ≤ g_j ≤ 10^8）。
输出
如果所描述的情况不可能，输出 -1。否则，输出男孩们可能送出的、且能满足所有条件的最少糖果总数。
样例
输入
3 2
1 2 1
3 4
输出
12
输入
2 2
0 1
1 0
输出
-1
输入
2 3
1 0
1 1 2
输出
4
提示
在第一个测试中，男孩们可能送出的最少糖果总数等于 12。例如，这可以是：第一个男孩分别送给第一个和第二个女孩 1 和 4 颗糖果，第二个男孩分别送给第一个和第二个女孩 3 和 2 颗糖果，第三个男孩分别送给第一个和第二个女孩 1 和 1 颗糖果。容易看出，所有条件都满足，且糖果总数为 12。
在第二个测试中，男孩们不可能以这样的方式送糖果，使得所有陈述都满足。
在第三个测试中，男孩们可能送出的最少糖果总数等于 4。例如，这可以是：第一个男孩分别送给第一个、第二个、第三个女孩 1、1、2 颗糖果，第二个男孩没有给每个女孩送糖果。容易看出，所有条件都满足，且糖果总数为 4。
提示
难度 1500 · binary search, constructive algorithms, greedy