문제
푸앙이는 $H\times W$개의 방이 있는 건물에서 $N$개의 방을 모두 방문하려고 한다.
건물은 $H$층이고 각 층에 $W$개의 방이 있는 직사각형 모양이다. 각 층의 가장 왼쪽에 있는 방부터 순서대로 1ドル$호, 2ドル$호, $\cdots,ドル $W$호이다.
이 건물은 특이한 구조로 되어 있어 같은 층에 있는 인접한 방으로 이동하는 데는 1ドル$초가 걸리지만, 같은 호의 인접한 방으로 이동하는 데는 100ドル$초가 걸린다.
같은 층에 있는 인접한 방의 호수의 차는 1ドル$이고, 같은 호의 인접한 방의 층수의 차는 1ドル$이다.
푸앙이는 현재 1ドル$층 1ドル$호에 있다. 푸앙이가 방문하고자 하는 방의 위치가 방문 순서와 상관 없이 주어질 때, 주어진 $N$개의 방을 방문하는 데 걸리는 최소 시간을 구하시오.
출력
주어진 $N$개의 방을 방문하는 데 걸리는 최소 시간을 출력한다.
W3sicHJvYmxlbV9pZCI6IjI5NzYwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhYzc0XHViYjNjIFx1YmMyOVx1YmIzOFx1ZDU1OFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNDc4XHVjNTU5XHVjNzc0XHViMjk0ICRIXFx0aW1lcyBXJFx1YWMxY1x1Yzc1OCBcdWJjMjlcdWM3NzQgXHVjNzg4XHViMjk0IFx1YWM3NFx1YmIzY1x1YzVkMFx1YzExYyAkTiRcdWFjMWNcdWM3NTggXHViYzI5XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWJjMjlcdWJiMzhcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjNzRcdWJiM2NcdWM3NDAgJEgkXHVjZTM1XHVjNzc0XHVhY2UwIFx1YWMwMSBcdWNlMzVcdWM1ZDAgJFckXHVhYzFjXHVjNzU4IFx1YmMyOVx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1YmFhOFx1YzU5MVx1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1Y2UzNVx1Yzc1OCBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWJkODBcdWQxMzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjICQxJFx1ZDYzOCwgJDIkXHVkNjM4LCAkXFxjZG90cyQsICRXJFx1ZDYzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YWM3NFx1YmIzY1x1Yzc0MCBcdWQyYjlcdWM3NzRcdWQ1NWMgXHVhZDZjXHVjODcwXHViODVjIFx1YjQxOFx1YzViNCBcdWM3ODhcdWM1YjQgXHVhYzE5XHVjNzQwIFx1Y2UzNVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjNzc4XHVjODExXHVkNTVjIFx1YmMyOVx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHViMzcwXHViMjk0ICQxJFx1Y2QwOFx1YWMwMCBcdWFjNzhcdWI5YWNcdWM5YzBcdWI5Y2MsIFx1YWMxOVx1Yzc0MCBcdWQ2MzhcdWM3NTggXHVjNzc4XHVjODExXHVkNTVjIFx1YmMyOVx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHViMzcwXHViMjk0ICQxMDAkXHVjZDA4XHVhYzAwIFx1YWM3OFx1YjliMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzE5XHVjNzQwIFx1Y2UzNVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjNzc4XHVjODExXHVkNTVjIFx1YmMyOVx1Yzc1OCBcdWQ2MzhcdWMyMThcdWM3NTggXHVjYzI4XHViMjk0ICQxJFx1Yzc3NFx1YWNlMCwgXHVhYzE5XHVjNzQwIFx1ZDYzOFx1Yzc1OCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViYzI5XHVjNzU4IFx1Y2UzNVx1YzIxOFx1Yzc1OCBcdWNjMjhcdWIyOTQgJDEkXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ0NzhcdWM1NTlcdWM3NzRcdWIyOTQgXHVkNjA0XHVjN2FjICQxJFx1Y2UzNSAkMSRcdWQ2MzhcdWM1ZDAgXHVjNzg4XHViMmU0LiBcdWQ0NzhcdWM1NTlcdWM3NzRcdWFjMDAgXHViYzI5XHViYjM4XHVkNTU4XHVhY2UwXHVjNzkwIFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWM3NTggXHVjNzA0XHVjZTU4XHVhYzAwIFx1YmMyOVx1YmIzOCBcdWMyMWNcdWMxMWNcdWM2NDAgXHVjMGMxXHVhZDAwIFx1YzVjNlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjLCBcdWM4ZmNcdWM1YjRcdWM5YzQgJE4kXHVhYzFjXHVjNzU4IFx1YmMyOVx1Yzc0NCBcdWJjMjlcdWJiMzhcdWQ1NThcdWIyOTQgXHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWNkNWNcdWMxOGMgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmMyOVx1YmIzOFx1ZDU1OFx1YWNlMFx1Yzc5MCBcdWQ1NThcdWIyOTQgXHViYzI5XHVjNzU4IFx1YWMxY1x1YzIxOCAkTiQsIFx1YWM3NFx1YmIzY1x1Yzc1OCBcdWNlMzVcdWFjZmMgXHVkNjM4XHVjNzU4IFx1YWMxY1x1YzIxOCAkSCQsICRXJFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMSBcXGxlIE4gXFxsZSBIIFxcdGltZXMgVzskICQxIFxcbGUgSCBcXGxlIDFcXCwwMDA7JCAkMSBcXGxlIFcgXFxsZSAxMDApJDxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCAkTiRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWJjMjlcdWJiMzhcdWQ1NThcdWFjZTBcdWM3OTAgXHVkNTU4XHViMjk0IFx1YmMyOVx1Yzc1OCBcdWM3MDRcdWNlNThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjhcdWM5MTEgJGkkXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjMjlcdWM3NTggXHVjNzA0XHVjZTU4ICRYX2kkXHVjZTM1LCAkWV9pJFx1ZDYzOFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMSBcXGxlIFhfaSBcXGxlIEg7JCAkMSBcXGxlIFlfaSBcXGxlIFcpJDxcL3A+XHJcblxyXG48cD5cdWJjMjlcdWJiMzhcdWQ1NThcdWFjZTBcdWM3OTAgXHVkNTU4XHViMjk0IFx1YmMyOVx1Yzc1OCBcdWM3MDRcdWNlNThcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM4ZmNcdWM1YjRcdWM5YzQgJE4kXHVhYzFjXHVjNzU4IFx1YmMyOVx1Yzc0NCBcdWJjMjlcdWJiMzhcdWQ1NThcdWIyOTQgXHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWNkNWNcdWMxOGMgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyOTc2MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlZpc2l0aW5nIEJ1aWxkaW5ncyIsImRlc2NyaXB0aW9uIjoiPHA+UHVhbmcgaXMgdHJ5aW5nIHRvIHZpc2l0ICROJCByb29tcyBpbiBhIGJ1aWxkaW5nIHdpdGggJEhcXHRpbWVzIFckIHJvb21zLjxcL3A+XHJcblxyXG48cD5UaGUgYnVpbGRpbmcgaGFzICRIJCBmbG9vcnMsIGFuZCBlYWNoIGZsb29yIGhhcyAkVyQgcm9vbXMgaW4gYSByZWN0YW5ndWxhciBzaGFwZS4gVGhlIHJvb21zIGFyZSBudW1iZXJlZCBzZXF1ZW50aWFsbHkgZnJvbSB0aGUgbGVmdG1vc3Qgcm9vbSBvbiBlYWNoIGZsb29yLCBzdGFydGluZyB3aXRoICQxJCwgJDIkLCAkXFxjZG90cyQsICRXJC48XC9wPlxyXG5cclxuPHA+VGhpcyBidWlsZGluZyBoYXMgYSBwZWN1bGlhciBzdHJ1Y3R1cmUgd2hlcmUgbW92aW5nIGJldHdlZW4gYWRqYWNlbnQgcm9vbXMgb24gdGhlIHNhbWUgZmxvb3IgdGFrZXMgJDEkIHNlY29uZCwgYnV0IG1vdmluZyBiZXR3ZWVuIGFkamFjZW50IHJvb21zIG9mIHRoZSBzYW1lIHJvb20gbnVtYmVyIG9uIGRpZmZlcmVudCBmbG9vcnMgdGFrZXMgJDEwMCQgc2Vjb25kcy48XC9wPlxyXG5cclxuPHA+VGhlIGRpZmZlcmVuY2UgaW4gcm9vbSBudW1iZXJzIGZvciBhZGphY2VudCByb29tcyBvbiB0aGUgc2FtZSBmbG9vciBpcyAkMSQsIGFuZCB0aGUgZGlmZmVyZW5jZSBpbiBmbG9vciBudW1iZXJzIGZvciBhZGphY2VudCByb29tcyB3aXRoIHRoZSBzYW1lIHJvb20gbnVtYmVyIGlzICQxJC48XC9wPlxyXG5cclxuPHA+UHVhbmcgaXMgY3VycmVudGx5IGluIHJvb20gJDEkIG9uIHRoZSAkMSRzdCBmbG9vci4gR2l2ZW4gdGhlIGxvY2F0aW9ucyBvZiB0aGUgcm9vbXMmbmJzcDtQdWFuZyB3YW50cyB0byB2aXNpdCBpbiBubyBwYXJ0aWN1bGFyIG9yZGVyLCBkZXRlcm1pbmUgdGhlIG1pbmltdW0gdGltZSByZXF1aXJlZCB0byB2aXNpdCZuYnNwO3RoZSBnaXZlbiAkTiQgcm9vbXMuPFwvcD5cclxuIiwiaW5wdXQiOiJcclxuPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgZGVub3RpbmcgdGhlIG51bWJlciBvZiByb29tcyBQdWFuZyB3YW50cyB0byB2aXNpdCAkTiQsIHRoZSBudW1iZXIgb2YgZmxvb3JzICRIJCwgYW5kIHJvb21zIHBlciBmbG9vciAkVyQsIHNlcGFyYXRlZCBieSBzcGFjZXMuICQoMSBcXGxlIE4gXFxsZSBIIFxcdGltZXMgVzskICQxIFxcbGUgSCBcXGxlIDFcXCwwMDA7JCAkMSBcXGxlIFcgXFxsZSAxMDApJDxcL3A+XHJcblxyXG48cD5Gcm9tIHRoZSBzZWNvbmQgbGluZSBvbndhcmRzLCBvdmVyIHRoZSBuZXh0ICROJCBsaW5lcywgdGhlIGxvY2F0aW9ucyBvZiB0aGUgcm9vbXMgUHVhbmcgd2FudHMgdG8gdmlzaXQgYXJlIGdpdmVuLiBGb3IgdGhlICRpJC10aCBsaW5lLCB0d28gaW50ZWdlcnMgZGVub3RpbmcgdGhlIHJvb20mIzM5O3MgbG9jYXRpb24gJFhfaVx1MjAwYiQgYW5kICRZX2kkIGFyZSBnaXZlbiwgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuIEhlcmUsICRYX2lcdTIwMGIkIGFuZCAkWV9pJCBkZW5vdGUgdGhhdCBhIHJvb20gaXMmbmJzcDt0aGUmbmJzcDskWV9pJC1cdTIwMGJ0aCByb29tIG9mIHRoZSAkWF9pXHUyMDBiJC10aCBmbG9vci4mbmJzcDskKDEgXFxsZSBYX2kgXFxsZSBIOyQgJDEgXFxsZSBZX2kgXFxsZSBXKSQ8XC9wPlxyXG5cclxuPHA+VGhlIGxvY2F0aW9ucyBvZiB0aGUgcm9vbXMgUHVhbmcgd2FudHMgdG8gdmlzaXQgYXJlIGFsbCBkaXN0aW5jdC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG1pbmltdW0gdGltZSByZXF1aXJlZCB0byB2aXNpdCZuYnNwO3RoZSBnaXZlbiAkTiQgcm9vbXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==