← 返回题目列表

AtCoder · keyence2019_c

C. 考试和向导

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

大学生高桥必须接受 N 考试并全部通过。 目前,他的 准备就绪 为 i第次检查是 A_{i},根据他的调查,已知他至少需要准备 B_{i} 为了通过 i第次检查。

高桥认为自己可能无法通过所有考试,他决定请魔术师青木改变尽可能少的考试的准备状态,以便他能够通过所有考试,同时不改变总的准备状态。

对于 Takahashi,找到最小可能的索引数 i 这样 A_i 和 C_i 是不同的,对于一个序列 C_1, C_2, ..., C_{N} 满足以下条件:

  • 序列之和 A_1, A_2, ..., A_{N} 和序列之和 C_1, C_2, ..., C_{N} 相等。
  • 对于每个 i, B_i \leq C_i 成立。

如果这样的序列 C_1, C_2, ..., C_{N} 无法构造,打印 -1.

约束

  • 1 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • A_i 和 B_i 是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 ... A_{N}
B_1 B_2 ... B_{N}

输出

打印尽可能少的索引数 i 这样 A_i 和 C_i 是不同的,对于一个序列 C_1, C_2, ..., C_{N} 满足条件。 如果有这样一个序列 C_1, C_2, ..., C_{N} 无法构造,打印 -1.


示例输入 1

3
2 3 5
3 4 1

示例输出 1

3

(A_1, A_2, A_3) = (2, 3, 5) 和 (B_1, B_2, B_3) = (3, 4, 1)。如果不采取任何措施,他就无法通过第一、第二次考试。 索引的最小可能数量 i 这样 A_i 和 C_i 不同, 3,在以下情况下实现:

  • (C_1, C_2, C_3) = (3, 5, 2)

示例输入 2

3
2 3 3
2 2 1

示例输出 2

0

在这种情况下,他什么都不用做就能通过所有考试。


示例输入 3

3
17 7 1
25 6 14

示例输出 3

-1

这种情况下,无论做什么,他都无法通过所有的考试。


示例输入 4

12
757232153 372327760 440075441 195848680 354974235 458054863 463477172 740174259 615762794 632963102 529866931 64991604
74164189 98239366 465611891 362739947 147060907 118867039 63189252 78303147 501410831 110823640 122948912 572905212

示例输出 4

5