Julie had a spooky nightmare. She is stuck in a Jelly! She has to eat her way out. Being a smart human being, her sub-conscience created a very sophisticated jelly. The jelly is composed of blocks. Different parts of the jelly have varying densities. The densities of each block are represented by single digit number, 1 – 9. The jelly is a rectangular prism, with dimensions, ~X~, ~Y~ and ~Z~ signifying the length, height and width in blocks, respectively. Julie can only eat in the following directions: up, down, left, right, forward and backwards. While dreaming, Julie has an infinitely big stomach. However, she's dazed and wants to exit the jelly as quickly as possible. As the density of the block is directly correlated with the time it takes to eat, Julie wants to eat a block path with minimal total density. Find the minimum sum of densities of the blocks that Julie has to eat to exit the jelly. Julie exits the jelly once she reaches any side of the jelly.
Input begins with ~X~, ~Y~ and ~Z~ space separated on a single line, signifying the dimensions of the jelly. The next ~Z \times Y~ lines contain ~Z~ blocks of ~Y~ lines with ~X~ characters, denoting the densities of the blocks, or
J, to indicate the position of Julie.
~1 \le X, Y, Z \le 150~
Hint: You may need fast IO methods for this problem to pass large test cases.
Integer ~T~ denoting the minimum sum of the densities of jelly that Julie has to eat to exit the jelly.
3 3 3 989 898 989 989 8J8 989 989 878 989