[AdditionalFile2659.zip](file://AdditionalFile2659.zip?type=additional_file)

#2659. 「POI2007 R3」天然气管道 Gas Pipelines

标签: 传统 | 时间限制: 1000 ms | 内存限制: 32 MiB |

题目描述

译自 POI 2007 Stage 3. Day 1「Gazociągi」

平面上有 $n$ 个天然气井和中转站，从天然气井开始向 $x$ 轴正方向、$y$ 轴负方向建立管道连接到中转站，使得管道的总长度最小。

输入格式

第一行一个整数 $n (1 \le n \le 50\ 000)$，表示天然气井的数量，中转站的数量与天然气井的数量一样。

接下来 $n$ 行每行两个整数 $x_i, y_i (0 \le x_i, y_i \le 100\ 000)$，表示天然气井的坐标。

接下来 $n$ 行每行两个整数 $x_i', y_i' (0 \le x_i, y_i \le 100\ 000)$，表示中转站的坐标。

保证存在一个合法的方案。

输出格式

第一行输出一个整数，表示最小的管道总长度。

接下来 $n$ 行表示一组可能的方案，每行两个整数，分别表示用管道连接的天然气井和中转站的编号。

如果有多组解，可以输出任意一组。

样例

输入

3
3 5
1 2
4 3
6 3
5 2
2 1

输出

9
2 3
1 2
3 1