题目名称

田忌赛马

题目描述

田忌和齐王各拥有 $n$ 匹马，其中田忌的马速度依次为 $a_1, a_2, \ldots, a_n$ ，齐王的马速度依次为 $b_1, b_2, \ldots, b_n$ 。双方进行 $n$ 轮比赛，每轮各自挑选一匹未参赛的马参赛。若田忌的马速度大于齐王的马速度，田忌得 1 分；若齐王的马速度大于田忌的马速度，齐王得 1 分；若两匹马速度相等，双方均不得分。已知齐王按固定顺序选马参赛，求田忌采用何种策略能使自己的得分减去齐王的得分的差值达到最大。

输入格式

1. 第一行输入单个整数 $n$，代表双方马匹的数量。
2. 第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ，表示田忌的马的速度。
3. 第三行输入 $n$ 个整数 $b_1, b_2, \ldots, b_n$ ，表示齐王的马的速度。

输出格式

输出单个整数，即田忌得分减去齐王得分的最大值。

数据范围

• 对于 $30\%$ 的数据，$n \leq 20$ 。
• 对于 $60\%$ 的数据，$n \leq 2000$ 。
• 对于 $100\%$ 的数据，$n \leq 200,000$ ，且 $1 \leq a_i, b_i \leq 1,000,000$ 。

输入输出样例

输入样例

3
10 20 30
15 25 35

输出样例

1