문제
상근이가 살고 있는 도시에는 큰 강이 흐르고 있고, 모든 사람의 집은 이 강 근처에 있다. 집은 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번 집으로 가기 위해서 이동해야 하는 거리의 최솟값을 구하는 프로그램을 작성하시오.
출력
첫째 줄에 상근이의 이동 거리의 최솟값을 출력한다.
W3sicHJvYmxlbV9pZCI6IjI4MzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMThcdWMwYzEgXHVkMGRkXHVjMmRjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWIzYzRcdWMyZGNcdWM1ZDBcdWIyOTQgXHVkMDcwIFx1YWMxNVx1Yzc3NCBcdWQ3NTBcdWI5NzRcdWFjZTAgXHVjNzg4XHVhY2UwLCBcdWJhYThcdWI0ZTAgXHVjMGFjXHViNzhjXHVjNzU4IFx1YzlkMVx1Yzc0MCBcdWM3NzQgXHVhYzE1IFx1YWRmY1x1Y2M5OFx1YzVkMCBcdWM3ODhcdWIyZTQuIFx1YzlkMVx1Yzc0MCAwXHViYzg4XHViZDgwXHVkMTMwIE1cdWJjODhcdWFlNGNcdWM5YzAgXHVhYzE1XHVjNzQ0IFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVjNzc4XHVjODExXHVkNTVjIFx1YzlkMSBcdWMwYWNcdWM3NzRcdWM3NTggXHVhYzcwXHViOWFjXHViMjk0IFx1YmFhOFx1YjQ1MCAxIFx1ZDBhY1x1Yjg1Y1x1YmJmOFx1ZDEzMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IDBcdWJjODggXHVjOWQxXHVjNWQwIFx1YzBiNFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1YmNmNFx1ZDJiOFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVjMGFjXHViNzhjXHViNGU0XHVjNzQ0IFx1YzZiNFx1YzFhMVx1ZDU1OFx1YjI5NCBcdWM3N2NcdWM3NDQgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjI0XHViMjk4XHVjNzQwIFx1YzgwMFx1YjE0MVx1YjU0Y1x1YWU0Y1x1YzljMCBNXHViYzg4IFx1YzlkMVx1YzczY1x1Yjg1YyBcdWFjMDBcdWM1N2NcdWQ1NWNcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBNXHViYzg4IFx1YzlkMVx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyOTQgXHVhZTM4XHVjNWQwIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0NCBcdWQwZGNcdWM2Y2NcdWM4ZmNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MjRcdWIyOTggXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzIxOFx1YzBjMSBcdWQwZGRcdWMyZGNcdWI5N2MgXHVkMGMwXHViODI0XHVhY2UwIFx1ZDU1OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NDAgXHVjZDFkIE5cdWJhODVcdWM3NzRcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFjMDEgXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1ZDBkMVx1YzJiOVx1ZDU2MCBcdWM3MDRcdWNlNThcdWM2NDAgXHViYWE5XHVjODAxXHVjOWMwXHViOTdjIFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWJjZjRcdWQyYjhcdWIyOTQgXHViOWU0XHVjNmIwIFx1Y2VlNFx1YzExYyBOXHViYTg1IFx1YmFhOFx1YjQ1MCBcdWJjZjRcdWQyYjhcdWM1ZDAgXHVkMGRjXHVjNmI4IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzBhY1x1Yjc4YyBBXHVhYzAwIDJcdWJjODggXHVjOWQxXHVjNWQwXHVjMTFjIDhcdWJjODhcdWM3M2NcdWI4NWMgXHVhYzAwXHViODI0XHVhY2UwIFx1ZDU1OFx1YWNlMCwgQlx1YWMwMCA2XHVjNWQwXHVjMTFjIDRcdWI4NWMgXHVhYzAwXHViODI0XHVhY2UwIFx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWI5N2MgXHVjMGRkXHVhYzAxXHVkNTc0XHViY2Y0XHVjNzkwLiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgMFx1YmM4OCBcdWM5ZDFcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTc0XHVjMTFjLCAyXHViYzg4XHVjNWQwXHVjMTFjIEFcdWI5N2MgXHVkMGRjXHVjNmIwXHVhY2UwLCA2XHViYzg4XHVjNWQwXHVjMTFjIEJcdWI5N2MgXHVkMGRjXHVjNmI4IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyA0XHViODVjIFx1YjNjY1x1YzU0NFx1YWMwMCBCXHViOTdjIFx1YjBiNFx1YjgyNFx1YzhmY1x1YWNlMCwgOFx1YmM4OFx1YzVkMFx1YzExYyBBXHViOTdjIFx1YjBiNFx1YjgyNFx1YjJlNFx1YzkwMFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0Y1x1YzVkMCBcdWM2ZDBcdWI3OTggXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YWMwMFx1YjgyNFx1YWNlMCBcdWQ1ODhcdWIzNTggTVx1YmM4OCBcdWM5ZDFcdWM3M2NcdWI4NWMgXHVhYzAwXHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YmFhOFx1YjRlMCBcdWMwYWNcdWI3OGNcdWM3NDQgXHViMzcwXHViODI0XHViMmU0XHVjOGZjXHVhY2UwLCBNXHViYzg4IFx1YzlkMVx1YzczY1x1Yjg1YyBcdWFjMDBcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1Yzc3NFx1YjNkOVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVhYzcwXHViOWFjXHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKE4gJmxlOyAzMDAsMDAwLCAzICZsZTsgTSAmbGU7IDEwPHN1cD45PFwvc3VwPik8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzIxOFx1YzBjMSBcdWQwZGRcdWMyZGNcdWI5N2MgXHVkMGMwXHViMjk0IFx1YzcwNFx1Y2U1OFx1YzY0MCBcdWJhYTlcdWM4MDFcdWM5YzBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjMjE4XHViMjk0IDBcdWFjZmMgTSBcdWMwYWNcdWM3NzQgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1Yzc3NFx1YjNkOSBcdWFjNzBcdWI5YWNcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyODM2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUklKRUtBIiwiZGVzY3JpcHRpb24iOiI8cD5JbiB0aGUgZmFyIGF3YXkgbGFuZCB0aGVyZSBpcyBhIGJpZyByaXZlciBhbmQgYSBudW1iZXIgb2YgdmlsbGFnZXMgYmVzaWRlIGl0LiBWaWxsYWdlcyBhcmUgbnVtYmVyZWQgMCB0aHJvdWdoIE0sIGluIG9yZGVyIGFsb25nIHRoZSByaXZlci4gRGlzdGFuY2UgYmV0d2VlbiBjb25zZWN1dGl2ZSB2aWxsYWdlcyBpcyBleGFjdGx5IDEgbWlsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TWlya28gbGl2ZXMgaW4gdGhlIHZpbGxhZ2UgbWFya2VkIHdpdGggMC4gSGUgaXMgaW4gdGhlIGJ1c2luZXNzIG9mIHRyYW5zcG9ydGluZyBwZW9wbGUgYmV0d2VlbiB2aWxsYWdlcyB3aXRoIGhpcyBib2F0LiBUb2RheSwgTWlya28gd2lsbCB0cmF2ZWwgZnJvbSBoaXMgdmlsbGFnZSB0byB2aWxsYWdlIE0sIGFuZCBoZSB3aWxsIGFsc28gdHJhbnNwb3J0IHNvbWUgcGVvcGxlIGFsb25nIHRoZSB3YXkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZXJlIGFyZSBOIHBlb3BsZSB0aGF0IHdpc2ggdG8gdHJhdmVsIHRvZGF5LCBhbmQgZm9yIGVhY2ggb2YgdGhlbSB3ZSBrbm93IHRoZWlyIHN0YXJ0aW5nIHBvaW50IGFzIHdlbGwgYXMgdGhlaXIgZGVzdGluYXRpb24uIE1pcmtvJiMzOTtzIGJvYXQgY2FuIGFjY29tbW9kYXRlIGFzIG1hbnkgcGVvcGxlIGFzIG5lZWRlZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TGV0JiMzOTtzIHNheSBmb3IgZXhhbXBsZSB0aGF0IHBlcnNvbiBBIGlzIHRyYXZlbGluZyBmcm9tIHZpbGxhZ2UgMiB0byB2aWxsYWdlIDgsIGFuZCBCIGZyb20gdmlsbGFnZSA2IHRvIHZpbGxhZ2UgNC4gTWlya28gd2lsbCwgYXMgYWx3YXlzLCBzdGFydCBmcm9tIGhpcyB2aWxsYWdlIDAsIHBpY2sgdXAgQSBhdCB2aWxsYWdlIDIsIHBpY2t1cCBCIGF0IDYsIGdvIGJhY2sgdG8gNCBhbmQgbGVhdmUgQiB0aGVyZSwgcHJvY2VlZCB0byB2aWxsYWdlIDgsIGxlYXZlIEEgdGhlcmUsIGFuZCB0aGVuIGNvbnRpbnVlIHRvIGhpcyBmaW5hbCBkZXN0aW5hdGlvbiwgdmlsbGFnZSBNLiBUaGlzIHNjZW5hcmlvIGlzIGdpdmVuIGluIHRoZSBmaXJzdCB0ZXN0IGNhc2UgYmVsb3cuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgZmluZCB0aGUgbWluaW11bSBudW1iZXIgb2YgbWlsZXMgdGhhdCBNaXJrbyBtdXN0IHRyYXZlbCBpbiBvcmRlciB0byB0cmFuc3BvcnQgZXZlcnlvbmUgdG8gdGhlaXIgZGVzdGluYXRpb25zIGFuZCByZWFjaCB2aWxsYWdlIE0gYXQgdGhlIGVuZC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGludGVnZXJzIE4gYW5kIE0gKE4gJmxlOyAzMDAgMDAwLCAzICZsZTsgTSAmbGU7IDEwPHN1cD45PFwvc3VwPikuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWluIHR3byBpbnRlZ2Vycywgc3RhcnRpbmcgcG9pbnQgYW5kIGRlc3RpbmF0aW9uIGZvciBlYWNoIHZpbGxhZ2VycyB0aGF0IHdhbnQmIzM5O3MgdG8gdHJhdmVsIHRvZGF5LiBUaGVzZSBudW1iZXIgd2lsbCBiZSBpbiByYW5nZSAwIHRvIE0uJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBtaW5pbXVtIG51bWJlciBvZiBtaWxlcyB0aGF0IE1pcmtvIG11c3QgdHJhdmVsLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d