서쪽의 노을을 바라보고 있는 꽃게 연준이가 광활한 모래밭의 한복판(1, 1)에서 자신의 집(M, N)까지 가려고 한다. 알다시피, 꽃게는 옆으로만 움직일 수 있기 때문에 처음에는 연준이가 남/북으로만 움직일 수 있다.

한편, 모래밭에는 K개의 돌림판이 있어서 돌림판 위에서는 연준이가 90도 회전할 수 있다. (정확히 90도씩만 회전할 수 있다.) 이 점을 이용해서 연준이는 돌림판을 잘 사용해서 날이 어둑어둑해지기 전에 빨리 집으로 가려고 한다.

연준이가 1만큼 움직이거나 90도 회전할 때 1의 시간이 걸린다고 할 때, 연준이가 집으로 갈 때 걸리는 최소 시간을 구하여라. 단, 동/서쪽으로 1만큼 움직이면 x좌표가 1/-1씩 증가하며, 남/북쪽으로 1만큼 움직이면 y좌표가 -1/1씩 증가한다.

꽃게 timer 2초 memory 256MB

꽃게 2초 256MB