#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部定数
#define D_ON			1										// 汎用フラグ - ON
#define D_OFF			0										// 汎用フラグ - OFF
#define D_TOWN_MAX		100000									// 最大街数
#define D_WAY_X			0										// 方向 - X
#define D_WAY_Y			1										// 方向 - Y

// 内部構造体 - 街位置情報
typedef struct Pos {
	int miTNo;													// 街番号 0～
	int miPos;													// 位置
} Pos;

// 内部構造体 - 街情報
typedef struct Town {
	int miX;													// 街位置 - X
	int miY;													// 街位置 - Y
} Town;

// 内部構造体 - ヒープ情報
typedef struct Heap {
	int miFNo;													// 街番号 - 元 0～
	int miTNo;													// 街番号 - 先 0～
	int miVal;													// 金額
} Heap;

// 内部変数
static Pos sz1PosX[D_TOWN_MAX];									// 街位置 - X方向
static Pos sz1PosY[D_TOWN_MAX];									// 街位置 - Y方向
static int siTCnt;												// 街数
static Town sz1Town[D_TOWN_MAX];								// 街情報
static int si1Conv[D_TOWN_MAX];									// 結合フラグ
static Heap sz1Heap[D_TOWN_MAX * 4];							// ヒープ
static int siHCnt;												// ヒープ数

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpT, *szpFpA;
#endif

// ソート関数 - 街位置 - 位置昇順
int
fSortFnc(
	const void *pzpVal1			// <I> 値１
	, const void *pzpVal2		// <I> 値２
)
{
	Pos *lzpVal1 = (Pos *)pzpVal1;
	Pos *lzpVal2 = (Pos *)pzpVal2;

	// 位置昇順
	if (lzpVal1->miPos > lzpVal2->miPos) {
		return(1);
	}
	else if (lzpVal1->miPos < lzpVal2->miPos) {
		return(-1);
	}

	return 0;
}

// ヒープ - 親子関係チェック
// 戻り値：[>=0]:変更した子の配列番号 [-1]:変更なし
int
fHeapChk(
	int piPNo					// <I> 親の配列番号 0～
)
{
	// 最小値
	int liMNo = piPNo;

	// 左の子と比較
	int liCNo = piPNo * 2 + 1;
	if (liCNo < siHCnt) {
		if (sz1Heap[liMNo].miVal > sz1Heap[liCNo].miVal) {
			liMNo = liCNo;
		}
	}

	// 右の子と比較
	liCNo = piPNo * 2 + 2;
	if (liCNo < siHCnt) {
		if (sz1Heap[liMNo].miVal > sz1Heap[liCNo].miVal) {
			liMNo = liCNo;
		}
	}

	// 自分が最小値であるかチェック
	if (piPNo == liMNo) {
		return -1;
	}

	// 値の交換
	Heap lzWork;
	memcpy(&lzWork, &sz1Heap[liMNo], sizeof(Heap));
	memcpy(&sz1Heap[liMNo], &sz1Heap[piPNo], sizeof(Heap));
	memcpy(&sz1Heap[piPNo], &lzWork, sizeof(Heap));

	return liMNo;
}

// ヒープ - キュー追加
int
fHeapEnqueue(
	int piFNo					// <I> 街番号 - 元 0～
	, int piTNo					// <I> 街番号 - 先 0～
	, int piVal					// <I> 金額
)
{
	int liRet;

	// 結合フラグ
	if (si1Conv[piTNo] != D_OFF) {
		return 0;
	}

	// 末尾に追加
	sz1Heap[siHCnt].miFNo = piFNo;
	sz1Heap[siHCnt].miTNo = piTNo;
	sz1Heap[siHCnt].miVal = piVal;
	siHCnt++;

	// 親子関係チェック
	int liNo = siHCnt - 1;
	while (1) {

		// 親の配列番号
		liNo = (liNo - 1) / 2;

		// 親子関係チェック
		liRet = fHeapChk(liNo);
		if (liRet < 0) {
			break;
		}
	}

	return 0;
}

// ヒープ - キュー取得
int
fHeapDequeue(
	Heap *pzpRet				// <O> 取得先
)
{
	// データ数
	if (siHCnt < 1) {
		return -1;
	}

	// 取得
	memcpy(pzpRet, &sz1Heap[0], sizeof(Heap));
	siHCnt--;

	// データ数
	if (siHCnt < 1) {
		return 0;
	}

	// 末尾を先頭へ
	memcpy(&sz1Heap[0], &sz1Heap[siHCnt], sizeof(Heap));

	// 親子関係チェック
	int liNo = 0;
	while (liNo >= 0) {
		liNo = fHeapChk(liNo);
	}

	return 0;
}

// 街単位での処理
int
fTownOne(
	int piTNo					// <I> 街番号 0～
)
{
	// 結合フラグ
	if (si1Conv[piTNo] != D_OFF) {
		return 0;
	}
	si1Conv[piTNo] = D_ON;

	// ヒープ - キュー追加 - X方向
	int liNo = sz1Town[piTNo].miX;
	if (liNo > 0) {
		fHeapEnqueue(piTNo, sz1PosX[liNo - 1].miTNo, sz1PosX[liNo].miPos - sz1PosX[liNo - 1].miPos);
	}
	if (liNo < siTCnt - 1) {
		fHeapEnqueue(piTNo, sz1PosX[liNo + 1].miTNo, sz1PosX[liNo + 1].miPos - sz1PosX[liNo].miPos);
	}

	// ヒープ - キュー追加 - X方向
	liNo = sz1Town[piTNo].miY;
	if (liNo > 0) {
		fHeapEnqueue(piTNo, sz1PosY[liNo - 1].miTNo, sz1PosY[liNo].miPos - sz1PosY[liNo - 1].miPos);
	}
	if (liNo < siTCnt - 1) {
		fHeapEnqueue(piTNo, sz1PosY[liNo + 1].miTNo, sz1PosY[liNo + 1].miPos - sz1PosY[liNo].miPos);
	}

	return 0;
}

// 実行メイン
int
fMain(
	int piTNo					// <I> テスト番号 1～
)
{
	int i, liRet;
	char lc1Buf[1024], lc1Out[1024];

	// データ初期化
	memset(si1Conv, D_OFF, sizeof(si1Conv));					// 結合フラグ
	siHCnt = 0;													// ヒープ数

	// テストファイルオープン
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", piTNo);
	szpFpT = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", piTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#endif

	// 街数取得
#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpT);
#else
	fgets(lc1Buf, sizeof(lc1Buf), stdin);
#endif
	sscanf(lc1Buf, "%d", &siTCnt);

	// 街位置取得
	for (i = 0; i < siTCnt; i++) {
#ifdef D_TEST
		fgets(lc1Buf, sizeof(lc1Buf), szpFpT);
#else
		fgets(lc1Buf, sizeof(lc1Buf), stdin);
#endif
		sscanf(lc1Buf, "%d%d", &sz1PosX[i].miPos, &sz1PosY[i].miPos);

		// 街番号
		sz1PosX[i].miTNo = i;
		sz1PosY[i].miTNo = i;
	}

	// 街位置 - ソート
	qsort(sz1PosX, siTCnt, sizeof(Pos), fSortFnc);
	qsort(sz1PosY, siTCnt, sizeof(Pos), fSortFnc);

	// 街情報 - セット
	for (i = 0; i < siTCnt; i++) {
		sz1Town[sz1PosX[i].miTNo].miX = i;
	}
	for (i = 0; i < siTCnt; i++) {
		sz1Town[sz1PosY[i].miTNo].miY = i;
	}

	// 最短距離取得
	int liMin = INT_MAX;
	int liWay, liNo;
	for (i = 0; i < siTCnt - 1; i++) {
		int liLen = sz1PosX[i + 1].miPos - sz1PosX[i].miPos;
		if (liMin > liLen) {
			liMin = liLen;
			liWay = D_WAY_X;
			liNo = i;
		}
	}
	for (i = 0; i < siTCnt - 1; i++) {
		int liLen = sz1PosY[i + 1].miPos - sz1PosY[i].miPos;
		if (liMin > liLen) {
			liMin = liLen;
			liWay = D_WAY_Y;
			liNo = i;
		}
	}

	// 初期結合街
	int liNo1, liNo2;
	if (liWay == D_WAY_X) {
		liNo1 = sz1PosX[liNo].miTNo;
		liNo2 = sz1PosX[liNo + 1].miTNo;
	}
	else {
		liNo1 = sz1PosY[liNo].miTNo;
		liNo2 = sz1PosY[liNo + 1].miTNo;
	}

	// ヒープ - キュー追加
	fHeapEnqueue(liNo1, liNo2, liMin);

	// 金額合計
	long long llSum = 0;
	while (1) {

		// ヒープ - キュー取得
		Heap lzHeap;
		liRet = fHeapDequeue(&lzHeap);
		if (liRet != 0) {
			break;
		}

		// 結合フラグ
		if (si1Conv[lzHeap.miFNo] != D_OFF) {
			if (si1Conv[lzHeap.miTNo] != D_OFF) {
				continue;
			}
		}

		// 金額加算
		llSum += (long long)lzHeap.miVal;

		// 街単位での処理
		fTownOne(lzHeap.miFNo);
		fTownOne(lzHeap.miTNo);
	}

	// 結果セット
	sprintf(lc1Out, "%lld\n", llSum);

	// 結果表示
#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, lc1Out)) {
		siRes = -1;
	}
#else
	printf("%s", lc1Out);
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpT);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", piTNo);
	}
	else {
		printf("NG %d\n", piTNo);
	}
#endif

	return 0;
}

int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		fMain(i);
	}
#else
	fMain(0);
#endif

	return 0;
}



Measured memory_bytes: 5484