On an n * m board there is a lemming on each square. Every second, the lemmings try to move either north, south, east or west, according to rules which are explained below. To determine which direction to move in, each lemming has an agenda, which is an ordering of the four possible directions (for example, one possible agenda might be NWES). The rules for lemming movement are the following:
1. Initially each lemming sets its direction of movement D to the first direction in its agenda.
2. At each time step, each lemming tries to move in its direction D. Three things can happen to lemming L:
(a) If L's current direction D causes it to move off the board, then the world has one less lemming in it. Otherwise, L's target destination will be to another square.
(b) If L's target square is empty or about to become empty as a result of another lemming leaving it, and no other lemming wants to move to the same square, then L moves into its target square. In this case, the lemming will use the same direction D in the next time step.
(c) Otherwise, if another lemming is trying to move into L's target square, or if the target square contains a lemming which cannot move, then L stays put. In this case, it will update its D by going to the next direction in its agenda (wrapping around to the beginning if necessary).
Two lemmings which want to exchange squares can do so, unless of course some other lemming is trying to move into one of their two squares (in which case all three of the lemmings would stay in their current squares). Lemmings being lemmings, they continue to move until all of them have moved off the board.
Your job is to determine how long that takes.