#D0895. 晚会配对

晚会配对

题目描述

晚会现场有两组嘉宾,分别是 AA 组和 BB 组,每组各有 nn 人。小 D 负责计算嘉宾们完成配对所需的总步数。

每位嘉宾都在平面直角坐标系中的一个点上。为了方便互动,只允许 AA 组嘉宾去找 BB 组嘉宾,且 AA 组嘉宾只能向东或向南走,每走一步距离为 11

现在要把 AA 组和 BB 组一一配对。每位 AA 组嘉宾必须恰好对应一位 BB 组嘉宾,每位 BB 组嘉宾也只能被配对一次。

请你计算所有 AA 组嘉宾走到对应 BB 组嘉宾位置的总步数。题目保证存在合法配对方案,而且无论如何配对,总步数都相同,所以不需要考虑具体配对方式。

输入格式

第一行一个正整数 nn,表示每组嘉宾的人数。

接下来 nn 行,每行两个整数,表示 AA 组一位嘉宾的坐标。

再接下来 nn 行,每行两个整数,表示 BB 组一位嘉宾的坐标。

输出格式

输出一个整数,表示总步数。

样例

3
3 5
1 2
4 3
6 3
5 2
2 1
9
1
2 4
5 1
6
2
1 5
3 2
4 4
6 1
8

样例解释

样例 1 中,总步数为 99

样例 2 中,唯一一对嘉宾需要走 52+41=6|5-2|+|4-1|=6 步。

样例 3 中,总步数为 88

数据范围与约定

子任务 分值 限制
11 3030 n8n \leq 8
22 7070 无特殊限制

对于 100%100\% 的数据,保证 1n500001 \leq n \leq 50000,且所有坐标都在 [0,100000][0,100000] 内。