#1122. 数列差分

数列差分

题目描述

小蓝有两个长度均为 nn 的数列 A={a1,a2,,an}A=\{a_1, a_2, \dots, a_n\}B={b1,b2,,bn}B=\{b_1, b_2, \dots, b_n\}。将两个数列作差定义为 $C = A - B = \{c_1=a_1-b_1, c_2=a_2-b_2, \dots, c_n=a_n-b_n\}$。

小蓝将对数列 BB 进行若干次操作。每次操作可以将数列 BB 中的任意一个数更改为任意一个整数。在进行完所有操作后,小蓝可以按任意顺序将数列 BB 重新排列,之后再计算数列 CC

小蓝想知道,最少操作多少次可以使得数列 CC 中的所有数都为正整数(即对于所有的 ii,都有 ci>0c_i > 0)。

输入格式

第一行包含一个正整数 nn —— 表示数列的长度。

第二行包含 nn 个整数 a1,a2,,ana_1, a_2, \dots, a_n —— 表示数列 AA 的元素,相邻整数之间使用一个空格分隔。

第三行包含 nn 个整数 b1,b2,,bnb_1, b_2, \dots, b_n —— 表示数列 BB 的元素,相邻整数之间使用一个空格分隔。

输出格式

输出一行,一个整数,表示使得数列 CC 中的所有数都为正整数所需的最少操作次数。

样例输入 1

4
22 31 12 14
3 19 27 44

样例输出 1

1

说明

样例解释

其中一种合法的操作方案是:将数列 BB 中的 4444 改为 00,之后将数列 BB 重新排列为 {19,27,3,0}\{19, 27, 3, 0\}

此时作差得到的数列 C={2219,3127,123,140}={3,4,9,14}C = \{22-19, 31-27, 12-3, 14-0\} = \{3, 4, 9, 14\},可见 CC 中所有的数均为正整数。整个过程只需要进行 11 次更改操作。

数据范围

  • 对于 30%30\% 的评测用例,保证 1n101 \le n \le 10
  • 对于 100%100\% 的评测用例,保证 1n1051 \le n \le 10^5
  • 对于 100%100\% 的评测用例,保证 109ai,bi109-10^9 \le a_i, b_i \le 10^9
  • 保证所有的输入数值均为整数。