该题作为 2025 年 4 月官方月赛 T3

题目描述

在村庄里，有一台蜂蜜酿造机，它每分钟可以酿造出一瓶任意容量的蜂蜜瓶。

有 $n$ 个村民排成一队。第 $i$ 个村民会在第 $t_i$ 分钟走到蜂蜜酿造机前，拿走当前已经酿造好的蜂蜜瓶中体积最大的一瓶。当第 $i$ 个村民拿到体积大于或等于 $a_i$ 的蜂蜜瓶时，他就会满意。如果此时没有蜂蜜瓶可供拿取，那么第 $i$ 个村民就会不满意。

那么，蜂蜜酿造机是否能够让所有村民都满意呢？如果不能，输出 -1。如果能，需要算出能让所有村民都满意所需酿造的蜂蜜瓶体积之和的最小值。

输入格式

第一行是一个整数 $n$（1 ≤ n ≤ 2 × 10^5），代表排队村民的数量。

接下来一行有 $n$ 个整数 $t_1,t_2,\cdots,t_n$（1 ≤ t1 ≤ t2 ≤ ⋯ ≤ tn ≤ 10^9），其中 $t_i$ 表示第 $i$ 个村民到达蜂蜜酿造机的时间。如果有两个村民到达时间相同，那么从左到右决定先后顺序。

接下来一行有 $n$ 个整数 $a_1,a_2,\cdots,a_n$（1 ≤ ai ≤ 10^9），其中 $a_i$ 表示第 $i$ 个村民对蜂蜜瓶体积的要求。

输出格式

如果不能让所有村民都满意，输出 -1。

否则输出一行，是一个整数，表示所需酿造的最小蜂蜜瓶体积之和。

输入输出样例

5
1 3 4 6 6
3 8 2 7 4

24

5
1 3 4 5 5
3 8 2 7 4

26

5
1 2 2 4 5
8 8 9 8 2

-1

说明 / 提示

数据范围与约定

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5,1 \le t_1 \le t_2 \le \cdots \le t_n \le 10^9,1 \le a_i \le 10^9$。