시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB34661370108638.052%

문제

상근이가 살고 있는 도시에는 큰 강이 흐르고 있고, 모든 사람의 집은 이 강 근처에 있다. 집은 0번부터 M번까지 강을 따라서 번호가 매겨져 있고, 인접한 집 사이의 거리는 모두 1 킬로미터이다.

상근이는 0번 집에 살고 있고, 보트를 이용해서 사람들을 운송하는 일을 하고 있다.

오늘은 저녁때까지 M번 집으로 가야한다. 상근이는 M번 집으로 가는 길에 사람들을 태워주려고 한다.

오늘 상근이의 수상 택시를 타려고 하는 사람은 총 N명이다. 상근이는 각 사람들이 탑승할 위치와 목적지를 알고 있다. 상근이의 보트는 매우 커서 N명 모두 보트에 태울 수 있다.

예를 들어, 사람 A가 2번 집에서 8번으로 가려고 하고, B가 6에서 4로 가려고 하는 경우를 생각해보자. 상근이는 0번 집에서 시작해서, 2번에서 A를 태우고, 6번에서 B를 태울 것이다. 그 다음 4로 돌아가 B를 내려주고, 8번에서 A를 내려다준다. 그 다음에 원래 상근이가 가려고 했던 M번 집으로 가면 된다.

상근이가 모든 사람을 데려다주고, M번 집으로 가기 위해서 이동해야 하는 거리의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. (N ≤ 300,000, 3 ≤ M ≤ 109)

다음 N개 줄에는 각 사람이 상근이의 수상 택시를 타는 위치와 목적지가 주어진다. 모든 숫자는 0과 M 사이이다.

출력

첫째 줄에 상근이의 이동 거리의 최솟값을 출력한다.

예제 입력 1

2 10
2 8
6 4

예제 출력 1

14

예제 입력 2

8 15
1 12
3 1
3 9
4 2
7 13
12 11
14 11
14 13

예제 출력 2

27
W3sicHJvYmxlbV9pZCI6IjI4MzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMThcdWMwYzEgXHVkMGRkXHVjMmRjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWIzYzRcdWMyZGNcdWM1ZDBcdWIyOTQgXHVkMDcwIFx1YWMxNVx1Yzc3NCBcdWQ3NTBcdWI5NzRcdWFjZTAgXHVjNzg4XHVhY2UwLCBcdWJhYThcdWI0ZTAgXHVjMGFjXHViNzhjXHVjNzU4IFx1YzlkMVx1Yzc0MCBcdWM3NzQgXHVhYzE1IFx1YWRmY1x1Y2M5OFx1YzVkMCBcdWM3ODhcdWIyZTQuIFx1YzlkMVx1Yzc0MCAwXHViYzg4XHViZDgwXHVkMTMwIE1cdWJjODhcdWFlNGNcdWM5YzAgXHVhYzE1XHVjNzQ0IFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVjNzc4XHVjODExXHVkNTVjIFx1YzlkMSBcdWMwYWNcdWM3NzRcdWM3NTggXHVhYzcwXHViOWFjXHViMjk0IFx1YmFhOFx1YjQ1MCAxIFx1ZDBhY1x1Yjg1Y1x1YmJmOFx1ZDEzMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IDBcdWJjODggXHVjOWQxXHVjNWQwIFx1YzBiNFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1YmNmNFx1ZDJiOFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVjMGFjXHViNzhjXHViNGU0XHVjNzQ0IFx1YzZiNFx1YzFhMVx1ZDU1OFx1YjI5NCBcdWM3N2NcdWM3NDQgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjI0XHViMjk4XHVjNzQwIFx1YzgwMFx1YjE0MVx1YjU0Y1x1YWU0Y1x1YzljMCBNXHViYzg4IFx1YzlkMVx1YzczY1x1Yjg1YyBcdWFjMDBcdWM1N2NcdWQ1NWNcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBNXHViYzg4IFx1YzlkMVx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyOTQgXHVhZTM4XHVjNWQwIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0NCBcdWQwZGNcdWM2Y2NcdWM4ZmNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MjRcdWIyOTggXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzIxOFx1YzBjMSBcdWQwZGRcdWMyZGNcdWI5N2MgXHVkMGMwXHViODI0XHVhY2UwIFx1ZDU1OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NDAgXHVjZDFkIE5cdWJhODVcdWM3NzRcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFjMDEgXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1ZDBkMVx1YzJiOVx1ZDU2MCBcdWM3MDRcdWNlNThcdWM2NDAgXHViYWE5XHVjODAxXHVjOWMwXHViOTdjIFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWJjZjRcdWQyYjhcdWIyOTQgXHViOWU0XHVjNmIwIFx1Y2VlNFx1YzExYyBOXHViYTg1IFx1YmFhOFx1YjQ1MCBcdWJjZjRcdWQyYjhcdWM1ZDAgXHVkMGRjXHVjNmI4IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzBhY1x1Yjc4YyBBXHVhYzAwIDJcdWJjODggXHVjOWQxXHVjNWQwXHVjMTFjIDhcdWJjODhcdWM3M2NcdWI4NWMgXHVhYzAwXHViODI0XHVhY2UwIFx1ZDU1OFx1YWNlMCwgQlx1YWMwMCA2XHVjNWQwXHVjMTFjIDRcdWI4NWMgXHVhYzAwXHViODI0XHVhY2UwIFx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWI5N2MgXHVjMGRkXHVhYzAxXHVkNTc0XHViY2Y0XHVjNzkwLiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgMFx1YmM4OCBcdWM5ZDFcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTc0XHVjMTFjLCAyXHViYzg4XHVjNWQwXHVjMTFjIEFcdWI5N2MgXHVkMGRjXHVjNmIwXHVhY2UwLCA2XHViYzg4XHVjNWQwXHVjMTFjIEJcdWI5N2MgXHVkMGRjXHVjNmI4IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyA0XHViODVjIFx1YjNjY1x1YzU0NFx1YWMwMCBCXHViOTdjIFx1YjBiNFx1YjgyNFx1YzhmY1x1YWNlMCwgOFx1YmM4OFx1YzVkMFx1YzExYyBBXHViOTdjIFx1YjBiNFx1YjgyNFx1YjJlNFx1YzkwMFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0Y1x1YzVkMCBcdWM2ZDBcdWI3OTggXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YWMwMFx1YjgyNFx1YWNlMCBcdWQ1ODhcdWIzNTggTVx1YmM4OCBcdWM5ZDFcdWM3M2NcdWI4NWMgXHVhYzAwXHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YmFhOFx1YjRlMCBcdWMwYWNcdWI3OGNcdWM3NDQgXHViMzcwXHViODI0XHViMmU0XHVjOGZjXHVhY2UwLCBNXHViYzg4IFx1YzlkMVx1YzczY1x1Yjg1YyBcdWFjMDBcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1Yzc3NFx1YjNkOVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVhYzcwXHViOWFjXHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKE4gJmxlOyAzMDAsMDAwLCAzICZsZTsgTSAmbGU7IDEwPHN1cD45PFwvc3VwPik8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzIxOFx1YzBjMSBcdWQwZGRcdWMyZGNcdWI5N2MgXHVkMGMwXHViMjk0IFx1YzcwNFx1Y2U1OFx1YzY0MCBcdWJhYTlcdWM4MDFcdWM5YzBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjMjJiXHVjNzkwXHViMjk0IDBcdWFjZmMgTSBcdWMwYWNcdWM3NzRcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjNzc0XHViM2Q5IFx1YWM3MFx1YjlhY1x1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI4MzYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSSUpFS0EiLCJkZXNjcmlwdGlvbiI6IjxwPkluIHRoZSBmYXIgYXdheSBsYW5kIHRoZXJlIGlzIGEgYmlnIHJpdmVyIGFuZCBhIG51bWJlciBvZiB2aWxsYWdlcyBiZXNpZGUgaXQuIFZpbGxhZ2VzIGFyZSBudW1iZXJlZCAwIHRocm91Z2ggTSwgaW4gb3JkZXIgYWxvbmcgdGhlIHJpdmVyLiBEaXN0YW5jZSBiZXR3ZWVuIGNvbnNlY3V0aXZlIHZpbGxhZ2VzIGlzIGV4YWN0bHkgMSBtaWxlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5NaXJrbyBsaXZlcyBpbiB0aGUgdmlsbGFnZSBtYXJrZWQgd2l0aCAwLiBIZSBpcyBpbiB0aGUgYnVzaW5lc3Mgb2YgdHJhbnNwb3J0aW5nIHBlb3BsZSBiZXR3ZWVuIHZpbGxhZ2VzIHdpdGggaGlzIGJvYXQuIFRvZGF5LCBNaXJrbyB3aWxsIHRyYXZlbCBmcm9tIGhpcyB2aWxsYWdlIHRvIHZpbGxhZ2UgTSwgYW5kIGhlIHdpbGwgYWxzbyB0cmFuc3BvcnQgc29tZSBwZW9wbGUgYWxvbmcgdGhlIHdheS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlcmUgYXJlIE4gcGVvcGxlIHRoYXQgd2lzaCB0byB0cmF2ZWwgdG9kYXksIGFuZCBmb3IgZWFjaCBvZiB0aGVtIHdlIGtub3cgdGhlaXIgc3RhcnRpbmcgcG9pbnQgYXMgd2VsbCBhcyB0aGVpciBkZXN0aW5hdGlvbi4gTWlya28mIzM5O3MgYm9hdCBjYW4gYWNjb21tb2RhdGUgYXMgbWFueSBwZW9wbGUgYXMgbmVlZGVkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5MZXQmIzM5O3Mgc2F5IGZvciBleGFtcGxlIHRoYXQgcGVyc29uIEEgaXMgdHJhdmVsaW5nIGZyb20gdmlsbGFnZSAyIHRvIHZpbGxhZ2UgOCwgYW5kIEIgZnJvbSB2aWxsYWdlIDYgdG8gdmlsbGFnZSA0LiBNaXJrbyB3aWxsLCBhcyBhbHdheXMsIHN0YXJ0IGZyb20gaGlzIHZpbGxhZ2UgMCwgcGljayB1cCBBIGF0IHZpbGxhZ2UgMiwgcGlja3VwIEIgYXQgNiwgZ28gYmFjayB0byA0IGFuZCBsZWF2ZSBCIHRoZXJlLCBwcm9jZWVkIHRvIHZpbGxhZ2UgOCwgbGVhdmUgQSB0aGVyZSwgYW5kIHRoZW4gY29udGludWUgdG8gaGlzIGZpbmFsIGRlc3RpbmF0aW9uLCB2aWxsYWdlIE0uIFRoaXMgc2NlbmFyaW8gaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IHRlc3QgY2FzZSBiZWxvdy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBmaW5kIHRoZSBtaW5pbXVtIG51bWJlciBvZiBtaWxlcyB0aGF0IE1pcmtvIG11c3QgdHJhdmVsIGluIG9yZGVyIHRvIHRyYW5zcG9ydCBldmVyeW9uZSB0byB0aGVpciBkZXN0aW5hdGlvbnMgYW5kIHJlYWNoIHZpbGxhZ2UgTSBhdCB0aGUgZW5kLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgaW50ZWdlcnMgTiBhbmQgTSAoTiAmbGU7IDMwMCAwMDAsIDMgJmxlOyBNICZsZTsgMTA8c3VwPjk8XC9zdXA+KS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW4gdHdvIGludGVnZXJzLCBzdGFydGluZyBwb2ludCBhbmQgZGVzdGluYXRpb24gZm9yIGVhY2ggdmlsbGFnZXJzIHRoYXQgd2FudCYjMzk7cyB0byB0cmF2ZWwgdG9kYXkuIFRoZXNlIG51bWJlciB3aWxsIGJlIGluIHJhbmdlIDAgdG8gTS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG1pbGVzIHRoYXQgTWlya28gbXVzdCB0cmF2ZWwuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2011 > Croatian Olympiad in Informatics 2011 3번