← 返回比赛

已结束 GESP巅峰赛#34

← 上一题下一题 →

A7373 | $午枫的宝石容器$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

在一座宝库中，有 $N$ 颗宝石和 $N-1$ 个容器。 宝石编号为 $1 \sim N$，第 $i$ 颗宝石的大小为 $A_i$；容器编号为 $1 \sim N-1$，第 $i$ 个容器的容量为 $B_i$。 小午希望将每一颗宝石放入一个不同的容器中。为此，他可以进行如下操作： - 选择任意一个正整数 $x$，额外购买一个容量为 $x$ 的新容器； 然后，他需要将所有 $N$ 颗宝石分别放入 $N$ 个容器（包括原有的 $N-1$ 个容器和新购买的容器）中，并满足： - 每个容器最多放一颗宝石； - 一颗宝石只能放入容量不小于它大小的容器中。 由于容器容量越大成本越高，小午希望新购买的容器容量尽可能小。 请你判断是否存在一个可行的 $x$，使得所有宝石都能被放入容器中； 如果存在，请输出满足条件的最小 $x$；否则输出 $-1$。

输入格式

第一行输入一个整数 $n$，表示宝石的数量； 第二行输入 $n$ 个整数 $A_1, A_2, \ldots, A_n$，表示每颗宝石的大小； 第三行输入 $n-1$ 个整数 $B_1, B_2, \ldots, B_{n-1}$，表示已有容器的容量。

输出格式

输出一个整数，表示最小可行的容器容量 $x$；若不存在，则输出 $-1$。

输入输出样例

输入 #1

4
5 2 3 7
6 2 8

输出 #1

C++ 编辑器

输入

输出