Statement

While Luca was looking through old boxes in his attic, he found its old nokia phone, still working! So he decides to play his favorite game on it: Exploding Robot. The main character of the game is a robot, that starts at the top-left corner of a grid with N rows and M columns, and moves according to a given sequence of commands, each indicating a step to the right, down, left or up. The robot never leaves the grid. The game forces you to place K bombs in distinct cells of the grid (but not on the starting cell) before the robot starts moving. When the robot visits a cell containing a bomb, it explodes and the game ends. You like to watch the robot move, so you want to place the bombs in such a way that allows the robot to make as many moves as possible before it explodes (or he runs out of moves). What is the maximum number of moves the robot can make, if you place the bombs optimally? Note that the move that makes the robot step on a bomb is not counted.