시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 102 54 47 50.538%

문제

소가 길을 건너는 이유는 그냥 길이 많아서이다. 존의 농장에는 길이 너무 많아서, 길을 건너지 않고서는 별로 돌아다닐 수가 없다.

존의 농장에는 작은 정사각형 목초지가 N×N (3 ≤ N ≤ 100) 격자로 이루어져 있다. 농장의 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다. 이 농장에 사는 소 베시는 한 목초지에서 상하좌우로 인접한 다른 목초지로 이동할 수 있지만, 교통사고를 피하기 위해 차가 안 오는지 확인하고 길을 건너야 한다. 길을 건너는데는 T초 (0 ≤ T ≤ 1,000,000)가 걸린다.

존이 베시에게 체스 대결을 신청했다. 베시는 북서쪽 끝에 있는 목초지에서 남동쪽 끝에 있는 존의 집으로 가야 한다. 길이 멀기 때문에 베시는 가는 도중에 배가 고파진다. 그래서 길을 세 번 건널 때마다 목초지에 있는 풀을 먹어야 한다. 존의 집에 도착할 때도 마찬가지지만, 출발할 때는 해당되지 않는다. 목초지마다 풀이 자란 정도가 달라서, 풀을 먹는데 걸리는 시간도 다르다.

베시가 가능한 한 빨리 존의 집에 도착할 수 있도록 도와주자.

입력

첫 줄에 N과 T가 주어진다. 다음 N줄에는 목초지마다 풀을 먹는데 걸리는 시간이 N×N의 형태로 주어진다. 각각의 수는 모두 100,000 이하이다.

출력

베시가 존의 집까지 가는데 걸리는 최소 시간을 출력한다.

예제 입력 1

4 2
30 92 36 10
38 85 60 16
41 13 5 68
20 97 13 80

예제 출력 1

31

힌트

30에서 출발해서 가능한 한 빨리 도착하려면 10으로 간 뒤 풀을 먹고, 5로 간 뒤 풀을 먹고, 존의 집인 80으로 가야 한다. 길을 건너는 데 총 16초, 풀을 먹는데 총 15초가 걸린다.

W3sicHJvYmxlbV9pZCI6IjE0NDYxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMThjXHVhYzAwIFx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMDhcdWFjMDQgXHVjNzc0XHVjNzIwIDciLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzE4Y1x1YWMwMCBcdWFlMzhcdWM3NDQgXHVhYzc0XHViMTA4XHViMjk0IFx1Yzc3NFx1YzcyMFx1YjI5NCBcdWFkZjhcdWIwZTUgXHVhZTM4XHVjNzc0IFx1YjljZVx1YzU0NFx1YzExY1x1Yzc3NFx1YjJlNC4gXHVjODc0XHVjNzU4IFx1YjE4ZFx1YzdhNVx1YzVkMFx1YjI5NCBcdWFlMzhcdWM3NzQgXHViMTA4XHViYjM0IFx1YjljZVx1YzU0NFx1YzExYywgXHVhZTM4XHVjNzQ0IFx1YWM3NFx1YjEwOFx1YzljMCBcdWM1NGFcdWFjZTBcdWMxMWNcdWIyOTQgXHViY2M0XHViODVjIFx1YjNjY1x1YzU0NFx1YjJlNFx1YjJkMCBcdWMyMThcdWFjMDAgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4NzRcdWM3NTggXHViMThkXHVjN2E1XHVjNWQwXHViMjk0IFx1Yzc5MVx1Yzc0MCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHViYWE5XHVjZDA4XHVjOWMwXHVhYzAwIE4mdGltZXM7TiAoMyAmbGU7IE4gJmxlOyAxMDApIFx1YWNhOVx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiA8YSBocmVmPVwiaHR0cHM6XC9cL3d3dy5hY21pY3BjLm5ldFwvcHJvYmxlbVwvMTQ0NjlcIj5cdWIxOGRcdWM3YTVcdWM3NTggXHViYzE0XHVhZTY1XHVjNWQwXHViMjk0IFx1YjE5Mlx1Yzc0MCBcdWM2YjhcdWQwYzBcdWI5YWM8XC9hPlx1YWMwMCBcdWM3ODhcdWM1YjRcdWMxMWMgXHVjMThjXHVhYzAwIFx1YjE4ZFx1YzdhNSBcdWJjMTZcdWM3M2NcdWI4NWMgXHViMDk4XHVhYzA4IFx1Yzc3Y1x1Yzc0MCBcdWM1YzZcdWIyZTQuIFx1Yzc3NCBcdWIxOGRcdWM3YTVcdWM1ZDAgXHVjMGFjXHViMjk0IFx1YzE4YyBcdWJjYTBcdWMyZGNcdWIyOTQgXHVkNTVjIFx1YmFhOVx1Y2QwOFx1YzljMFx1YzVkMFx1YzExYyBcdWMwYzFcdWQ1NThcdWM4OGNcdWM2YjBcdWI4NWMgXHVjNzc4XHVjODExXHVkNTVjIFx1YjJlNFx1Yjk3OCBcdWJhYTlcdWNkMDhcdWM5YzBcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM5YzBcdWI5Y2MsIFx1YWQ1MFx1ZDFiNVx1YzBhY1x1YWNlMFx1Yjk3YyBcdWQ1M2NcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1Y2MyOFx1YWMwMCBcdWM1NDggXHVjNjI0XHViMjk0XHVjOWMwIFx1ZDY1NVx1Yzc3OFx1ZDU1OFx1YWNlMCBcdWFlMzhcdWM3NDQgXHVhYzc0XHViMTA4XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVhZTM4XHVjNzQ0IFx1YWM3NFx1YjEwOFx1YjI5NFx1YjM3MFx1YjI5NCBUXHVjZDA4ICgwICZsZTsgVCAmbGU7IDEsMDAwLDAwMClcdWFjMDAgXHVhYzc4XHViOWIwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4NzRcdWM3NzQgXHViY2EwXHVjMmRjXHVjNWQwXHVhYzhjIFx1Y2NiNFx1YzJhNCBcdWIzMDBcdWFjYjBcdWM3NDQgXHVjMmUwXHVjY2FkXHVkNTg4XHViMmU0LiBcdWJjYTBcdWMyZGNcdWIyOTQgXHViZDgxXHVjMTFjXHVjYWJkIFx1YjA1ZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYWE5XHVjZDA4XHVjOWMwXHVjNWQwXHVjMTFjIFx1YjBhOFx1YjNkOVx1Y2FiZCBcdWIwNWRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1Yzg3NFx1Yzc1OCBcdWM5ZDFcdWM3M2NcdWI4NWMgXHVhYzAwXHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVhZTM4XHVjNzc0IFx1YmE0MFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViY2EwXHVjMmRjXHViMjk0IFx1YWMwMFx1YjI5NCBcdWIzYzRcdWM5MTFcdWM1ZDAgXHViYzMwXHVhYzAwIFx1YWNlMFx1ZDMwY1x1YzljNFx1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1YWUzOFx1Yzc0NCBcdWMxMzggXHViYzg4IFx1YWM3NFx1YjExMCBcdWI1NGNcdWI5YzhcdWIyZTQgXHViYWE5XHVjZDA4XHVjOWMwXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWQ0ODBcdWM3NDQgXHViYTM5XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjODc0XHVjNzU4IFx1YzlkMVx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NjAgXHViNTRjXHViM2M0IFx1YjljOFx1Y2MyY1x1YWMwMFx1YzljMFx1YzljMFx1YjljYywgXHVjZDljXHViYzFjXHVkNTYwIFx1YjU0Y1x1YjI5NCBcdWQ1NzRcdWIyZjlcdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWJhYTlcdWNkMDhcdWM5YzBcdWI5YzhcdWIyZTQgXHVkNDgwXHVjNzc0IFx1Yzc5MFx1Yjc4MCBcdWM4MTVcdWIzYzRcdWFjMDAgXHViMmVjXHViNzdjXHVjMTFjLCBcdWQ0ODBcdWM3NDQgXHViYTM5XHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWIzYzQgXHViMmU0XHViOTc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjYTBcdWMyZGNcdWFjMDAgXHVhYzAwXHViMmE1XHVkNTVjIFx1ZDU1YyBcdWJlNjhcdWI5YWMgXHVjODc0XHVjNzU4IFx1YzlkMVx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjNjNFx1Yjg1ZCBcdWIzYzRcdWM2NDBcdWM4ZmNcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIE5cdWFjZmMgVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVjOTA0XHVjNWQwXHViMjk0IFx1YmFhOVx1Y2QwOFx1YzljMFx1YjljOFx1YjJlNCBcdWQ0ODBcdWM3NDQgXHViYTM5XHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NzQgTiZ0aW1lcztOXHVjNzU4IFx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWMyMThcdWIyOTQgXHViYWE4XHViNDUwIDEwMCwwMDAgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YmNhMFx1YzJkY1x1YWMwMCBcdWM4NzRcdWM3NTggXHVjOWQxXHVhZTRjXHVjOWMwIFx1YWMwMFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjZDVjXHVjMThjIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPGJyPjxcL3A+IiwiaGludCI6IjxwPjMwXHVjNWQwXHVjMTFjIFx1Y2Q5Y1x1YmMxY1x1ZDU3NFx1YzExYyBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVkNTVjIFx1YmU2OFx1YjlhYyBcdWIzYzRcdWNjMjlcdWQ1NThcdWI4MjRcdWJhNzQgMTBcdWM3M2NcdWI4NWMgXHVhYzA0IFx1YjRhNCBcdWQ0ODBcdWM3NDQgXHViYTM5XHVhY2UwLCA1XHViODVjIFx1YWMwNCBcdWI0YTQgXHVkNDgwXHVjNzQ0IFx1YmEzOVx1YWNlMCwgXHVjODc0XHVjNzU4IFx1YzlkMVx1Yzc3OCA4MFx1YzczY1x1Yjg1YyBcdWFjMDBcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFlMzhcdWM3NDQgXHVhYzc0XHViMTA4XHViMjk0IFx1YjM3MCBcdWNkMWQgMTZcdWNkMDgsIFx1ZDQ4MFx1Yzc0NCBcdWJhMzlcdWIyOTRcdWIzNzAgXHVjZDFkIDE1XHVjZDA4XHVhYzAwIFx1YWM3OFx1YjliMFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE0NDYxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiV2h5IERpZCB0aGUgQ293IENyb3NzIHRoZSBSb2FkIChHb2xkKSIsImRlc2NyaXB0aW9uIjoiPHA+V2h5IGRpZCB0aGUgY293IGNyb3NzIHRoZSByb2FkPyBXZWxsLCBvbmUgcmVhc29uIGlzIHRoYXQgRmFybWVyIEpvaG4mIzM5O3MgZmFybSBzaW1wbHkgaGFzIGEgbG90IG9mIHJvYWRzLCBtYWtpbmcgaXQgaW1wb3NzaWJsZSBmb3IgaGlzIGNvd3MgdG8gdHJhdmVsIGFyb3VuZCB3aXRob3V0IGNyb3NzaW5nIG1hbnkgb2YgdGhlbS48XC9wPlxyXG5cclxuPHA+RkomIzM5O3MgZmFybSBpcyBhcnJhbmdlZCBhcyBhbiZuYnNwO04mdGltZXM7TiBzcXVhcmUgZ3JpZCBvZiBmaWVsZHMgKDMgJmxlOyBOICZsZTsgMTAwKSwgd2l0aCBhIHNldCBvZiZuYnNwO04mbWludXM7MSBub3J0aC1zb3V0aCByb2FkcyBhbmQmbmJzcDtOJm1pbnVzOzEgZWFzdC13ZXN0IHJvYWRzIHJ1bm5pbmcgdGhyb3VnaCB0aGUgaW50ZXJpb3Igb2YgdGhlIGZhcm0gc2VydmluZyBhcyBkaXZpZGVycyBiZXR3ZWVuIHRoZSBmaWVsZHMuIEEgdGFsbCBmZW5jZSBydW5zIGFyb3VuZCB0aGUgZXh0ZXJuYWwgcGVyaW1ldGVyLCBwcmV2ZW50aW5nIGNvd3MgZnJvbSBsZWF2aW5nIHRoZSBmYXJtLiBCZXNzaWUgdGhlIGNvdyBjYW4gbW92ZSBmcmVlbHkgZnJvbSBhbnkgZmllbGQgdG8gYW55IG90aGVyIGFkamFjZW50IGZpZWxkIChub3J0aCwgZWFzdCwgc291dGgsIG9yIHdlc3QpLCBhcyBsb25nIGFzIHNoZSBjYXJlZnVsbHkgbG9va3MgYm90aCB3YXlzIGJlZm9yZSBjcm9zc2luZyB0aGUgcm9hZCBzZXBhcmF0aW5nIHRoZSB0d28gZmllbGRzLiBJdCB0YWtlcyBoZXImbmJzcDtUJm5ic3A7dW5pdHMgb2YgdGltZSB0byBjcm9zcyBhIHJvYWQgKDAgJmxlOyBUICZsZTsgMSwwMDAsMDAwKS48XC9wPlxyXG5cclxuPHA+T25lIGRheSwgRkogaW52aXRlcyBCZXNzaWUgdG8gdmlzaXQgaGlzIGhvdXNlIGZvciBhIGZyaWVuZGx5IGdhbWUgb2YgY2hlc3MuIEJlc3NpZSBzdGFydHMgb3V0IGluIHRoZSBub3J0aC13ZXN0IGNvcm5lciBmaWVsZCBhbmQgRkomIzM5O3MgaG91c2UgaXMgaW4gdGhlIHNvdXRoLWVhc3QgY29ybmVyIGZpZWxkLCBzbyBCZXNzaWUgaGFzIHF1aXRlIGEgd2FsayBhaGVhZCBvZiBoZXIuIFNpbmNlIHNoZSBnZXRzIGh1bmdyeSBhbG9uZyB0aGUgd2F5LCBzaGUgc3RvcHMgYXQgZXZlcnkgdGhpcmQgZmllbGQgc2hlIHZpc2l0cyB0byBlYXQgZ3Jhc3MgKG5vdCBpbmNsdWRpbmcgaGVyIHN0YXJ0aW5nIGZpZWxkLCBidXQgaW5jbHVkaW5nIHBvc3NpYmx5IHRoZSBmaW5hbCBmaWVsZCBpbiB3aGljaCBGSiYjMzk7cyBob3VzZSByZXNpZGVzKS4gU29tZSBmaWVsZHMgYXJlIGdyYXNzaWVyIHRoYW4gb3RoZXJzLCBzbyB0aGUgYW1vdW50IG9mIHRpbWUgcmVxdWlyZWQgZm9yIHN0b3BwaW5nIHRvIGVhdCBkZXBlbmRzIG9uIHRoZSBmaWVsZCBpbiB3aGljaCBzaGUgc3RvcHMuPFwvcD5cclxuXHJcbjxwPlBsZWFzZSBoZWxwIEJlc3NpZSBkZXRlcm1pbmUgdGhlIG1pbmltdW0gYW1vdW50IG9mIHRpbWUgaXQgd2lsbCB0YWtlIHRvIHJlYWNoIEZKJiMzOTtzIGhvdXNlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMmbmJzcDtOJm5ic3A7YW5kJm5ic3A7VC4gVGhlIG5leHQmbmJzcDtOJm5ic3A7bGluZXMgZWFjaCBjb250YWluJm5ic3A7TiZuYnNwO3Bvc2l0aXZlIGludGVnZXJzIChlYWNoIGF0IG1vc3QgMTAwLDAwMCkgZGVzY3JpYmluZyB0aGUgYW1vdW50IG9mIHRpbWUgcmVxdWlyZWQgdG8gZWF0IGdyYXNzIGluIGVhY2ggZmllbGQuIFRoZSBmaXJzdCBudW1iZXIgb2YgdGhlIGZpcnN0IGxpbmUgaXMgdGhlIG5vcnRoLXdlc3QgY29ybmVyLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IHRoZSBtaW5pbXVtIGFtb3VudCBvZiB0aW1lIHJlcXVpcmVkIGZvciBCZXNzaWUgdG8gdHJhdmVsIHRvIEZKJiMzOTtzIGhvdXNlLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5UaGUgb3B0aW1hbCBzb2x1dGlvbiBmb3IgdGhpcyBleGFtcGxlIGludm9sdmVzIG1vdmluZyBlYXN0IDMgc3F1YXJlcyAoZWF0aW5nIHRoZSAmcXVvdDsxMCZxdW90OyksIHRoZW4gbW92aW5nIHNvdXRoIHR3aWNlIGFuZCB3ZXN0IG9uY2UgKGVhdGluZyB0aGUgJnF1b3Q7NSZxdW90OyksIGFuZCBmaW5hbGx5IG1vdmluZyBzb3V0aCBhbmQgZWFzdCB0byB0aGUgZ29hbC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==