문제

초급 마법사들은 중급 마법사가 되기 위해 시험을 통과해야 합니다. 만약 통과하지 못한다면 중급 마법사로 승격할 수 없으며 다음 기회에 시험을 다시 봐야 합니다.

시험의 내용은 다음과 같습니다. 시험을 치르는 장소는 마법사의 숲이며, 그 숲에 들어가 출구를 찾아야합니다. 이때 지나가는 길에 나무가 가로막고 있으면 그냥 지나갈 수 없고, 10마력을 소비하면 그 나무를 통과해 지나갈 수 있습니다. 단, 연속된 2개 이상의 나무는 통과할 수 없습니다.

이렇게 마법을 쓰면서 가능한 한 빠르게 탈출하면 중급 마법사가 될 수 있습니다. 이 때, 마력을 만큼 가지고 있는 초급 마법사가 이 시험에서 통과하려면 최소 몇 초가 걸리는지 구하는 프로그램을 작성해주세요.

입력

첫째 줄에 마법사의 숲의 크기를 나타내는 세로길이를 , 가로길이 와 초급 마법사의 초기 마력 가 공백을 두고 주어집니다.
그 다음 개의 줄에 걸쳐 마법사의 숲에 대한 정보가 각 줄에 공백없이 주어집니다. 각 줄은 개의 문자로 구성되며 은 지나갈 수 있는 길을, 은 나무를 의미합니다. 인접한 곳으로 한 칸 이동할 때 초가 소요되며, 현재 위치에서 마력을 만큼 사용하여 인접한 나무의 다음칸으로 이동할 때도 초가 소요됩니다. 여기서 인접한 칸은 상하좌우 네 방향으로 맞닿아있는 칸을 의미합니다.

최초 시작 위치는 좌측 상단  위치이고, 출구는 우측 하단  위치입니다. 시작 자리와 출구 자리에는 나무가 없음이 보장됩니다.

• 
• 마법사의 숲에 대한 정보는  또는 로만 이루어진 문자열이다.
  
  

출력

마력을 만큼 가진 초급 마법사가 이 숲을 탈출하는 데 걸리는 최단 시간을 출력합니다. 단, 이 숲을 탈출할 수 없다면 -1을 출력합니다.