CF1158A The Party and Sweets

有 $n$ 个男孩和 $m$ 个女孩来参加聚会。每个男孩会送给每个女孩若干整数颗糖果（可能为零）。所有男孩编号为 $1$ 到 $n$，所有女孩编号为 $1$ 到 $m$。对于所有 $1 \leq i \leq n$，第 $i$ 个男孩送给某个女孩的最少糖果数为 $b_i$；对于所有 $1 \leq j \leq m$，第 $j$ 个女孩从某个男孩收到的最多糖果数为 $g_j$。 更正式地，设 $a_{i,j}$ 表示第 $i$ 个男孩送给第 $j$ 个女孩的糖果数。那么 $b_i$ 恰好等于 $a_{i,1}, a_{i,2}, \ldots, a_{i,m}$ 中的最小值，$g_j$ 恰好等于 $a_{1,j}, a_{2,j}, \ldots, a_{n,j}$ 中的最大值。 你需要计算男孩们可能送出的最少糖果总数，即最小化所有 $a_{i,j}$ 之和（$1 \leq i \leq n$，$1 \leq j \leq m$）。给定 $b_1, \ldots, b_n$ 和 $g_1, \ldots, g_m$，请计算这个最小值。

第一行包含两个整数 $n$ 和 $m$，用空格隔开，分别表示男孩和女孩的数量（$2 \leq n, m \leq 100\,000$）。 第二行包含 $n$ 个整数 $b_1, \ldots, b_n$，用空格隔开，其中 $b_i$ 表示第 $i$ 个男孩送给某个女孩的最少糖果数（$0 \leq b_i \leq 10^8$）。 第三行包含 $m$ 个整数 $g_1, \ldots, g_m$，用空格隔开，其中 $g_j$ 表示第 $j$ 个女孩从某个男孩收到的最多糖果数（$0 \leq g_j \leq 10^8$）。

如果不存在满足条件的分配方案，输出 $-1$。否则，输出男孩们可能送出的最少糖果总数。

在第一个测试样例中，男孩们可能送出的最少糖果总数为 $12$。例如，第一个男孩分别送给两个女孩 $1$ 和 $4$ 颗糖果，第二个男孩分别送 $3$ 和 $2$ 颗，第三个男孩分别送 $1$ 和 $1$ 颗。可以验证所有条件都满足，总糖果数为 $12$。 在第二个测试样例中，无法满足所有条件。 在第三个测试样例中，男孩们可能送出的最少糖果总数为 $4$。例如，第一个男孩分别送给三个女孩 $1$、$1$、$2$ 颗糖果，第二个男孩不给每个女孩送糖果。可以验证所有条件都满足，总糖果数为 $4$。 由 ChatGPT 4.1 翻译