The year is 2060. Global warming is getting so bad that it's causing floods everywhere, especially in Sadland. Barr the bear is stuck in Sadland and he needs to escape before the flood drowns him!
Fortunately, technology is so advanced now that it's possible to teleport from one place to another by entering a teleporter. And even more fortunately, there is a magical teleporter in Sadland that can teleport anyone to Happyland, which is free of floods! Obviously Barr wants to get to this teleporter before he drowns in the flood. However, Barr is also a very lazy bear taking his afternoon nap and would like to sleep for as long as possible before making his way to the teleporter. Your job is to help him find out the maximum amount of time he can sleep and still escape from Sadland in time.
Sadland is represented by a grid of N by N unit cells whose sides are parallel to the north-south and east-west directions. Some of the cells will have holes, one cell will be the magical teleporter, and the rest will be grassy cells. When Barr moves, he can make at most S steps per minute. A step is basically a move onto an adjacent grassy cell to the north, south, east, or west (he cannot walk into holes). Initially, Barr will be in his home on a grassy cell, and the floods will occupy several grassy cells. During each minute from this time onwards, the following events happen in order:
The first line contains integers N (1 ≤ N ≤ 800) and S (1 ≤ S ≤ 1,000) separated by a space.
The next N lines represent the Sadland grid. Each of these lines contains N characters, each representing a unit cell of the grid. H denotes a hole; G denotes a grassy cell; B denotes Barr's home, which is also on a grassy cell; T denotes the cell with the teleporter; and F denotes a flooded cell.
NOTE: It is guaranteed that the map will contain exactly one letter B, exactly one letter T and at least one letter F. It is also guaranteed that there is a sequence of adjacent letters G that connects Barr to the teleporter, as well as a sequence of adjacent letters G that connects at least one flooded cell to Barr's home (i.e., to Barr's initial location). These sequences might be as short as length zero, in case the teleporter or a flooded cell is adjacent to Barr's initial location. Also, note that the cell with the teleporter cannot be flooded.
7 3 HHHHHHH HGGGGGH HGGGGGH BGGGGGT HGGGGGH HGGGGGH HFFFFFH
7 3 HHHHHHH HGGGGGH HGGGGGH BGGGGGT HGGGGGH HGGGGGH HGFFGGH