seuOJ303 - 姬哥与卖菜

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：秋季, 校赛, 2020

题目描述

  “东南的CS的格局，是和别处不同的：都是年级里一个全连接的卷人层，层里面预备着激活函数，可以随时卷人。进来卷的人，期中期末考完试，每每互相卖个菜，亮个3.5的绩点，整一个奖学金，——这是多年前的事，现在保研要涨到90分。”
  姬哥也喜欢卖菜，总是满口“我是fw”，叫人半懂不懂的。但作为前任心理委员，姬哥知道卖菜不能太过，否则会让心理承受能力弱的同学受伤。
  这次班级的实验验收开始了，所有$n(1 \leq n \leq1 000000)$个同学排成了一条长队按顺序等待验收，队首的同学验收完毕后就会离开队伍。由于验收得很慢，所有同学都开始欢快地聊（卖）天（菜），而每个同学的卖菜水平不同，承受能力也不同：队伍中第$i$个同学卖菜的影响力为$a_i$，承受能力为$b_i$。当队伍中第$i$个同学完成验收离开队伍时，他会卖菜一次，并对队伍中的所有人造成$a_i$的心理压力。也就是说，队伍中第$i$个同学总共会受到$\sum_{j=1}^{i-1}a_j$的心理压力，而当该同学受到的心理压力大于等于他的承受能力$b_i$时，他会破防，破防值即为$(\sum_{j=1}^{i-1}a_j)-b_i$。特别地，第一位离开队伍的同学不会破防。现在姬哥想要履行心理委员的职责，他可以将所有同学以任意顺序重新排队，从而使得破防值最大的同学破防值最小。你可以帮姬哥计算出最优情况下破防值最大的同学的破防值么？

输入格式

输入数据共$3$行。
第一行一个正整数$n(1 \leq n \leq 1000000)$
第二行$n$个用空格分隔的整数$a_i$,第$i$个数表示队伍中第$i$个同学的卖菜影响力$a_i$
第三行$n$个用空格分隔的整数$b_i$,第$i$个数表示队伍中第$i$个同学的承受能力$b_i$
其中，$0 \leq a_i,b_i \leq 1000000000$

输出格式

输出共一行一个整数，表示最大的破防值。若无人破防，输出$-1$。

样例

样例输入

3
3 3 1
2 1 1

样例输出

2

样例解释

将队伍倒序即可，即$3$号同学放在队首，$1$号同学放在队尾。