SP10439 WALKROBO - Walking Robot

Walking Robot Leonard is a student of robotics, and his teacher, Dr. Cooper, asked his class to build a robot to interact with the environment and change its behavior upon certain events. The environment, behavior changes and the events are up to the student, so Leonard decided to make a robot that walks in a grid with a set of movements. There are downloading spots in the grid in which the robot can learn new movements. The task of the robot is to go from one point of the grid to another in as fewest steps as possible. The grid is composed of M rows and N columns of squares. The botton-left square is position (0,0) and the top-right square is position (N-1,M-1). A movement is defined as a tuple (X,Y). Where X denotes the movement on the x axis and Y on the y axis. A movement is considered as 1 step. The robot can not make a movement that will end outside the boundaries of the grid. There are K possible movements for the robot to learn. The robot stars with T movements on its memory. If the robot is in a downloading spot, he can choose to learn the movement available at that spot, this takes 1 step. The robot can not learn new movements while he is moving. The robot starts at position (0,0) and should move to position (N-1,M-1).

The first line has four integers M, N (2

For each test case print a single line with "Case #X: S" where X is the number of the test case (starting from 1) and S is the lowest number of steps to achieve the destination. If it is not possible for the robot to achieve the destination, print -1 instead of the number of steps.