RSI
---

This problem sounds difficult at first but actually turns out to be fairly straightforward
if you are familiar with dynamic programming.  The main stumbling block in this problem is
reading the problem statement carefully in order to understand all of the constraints stated
in the problem.

Here's a quick summary.
- You are typing with two fingers, which we denote as "L" and "R".
- Your fingers must always be hovering over valid keys on the keyboard.  At time 0, they're
  hovering over keys "4" and "5", respectively.
- In each turn, each finger moves vertically, horizontally, or presses a key, with the
  constraint that "L" is always to the left or "R" and that at most one finger can
  be pressing a key at a time (e.g., one finger may be pressing a key while the other finger
  moves to the right)

Let s[0...D-1] be a string of D digits.  We'll solve the problem using the following
recurrence:

digits[lr,lc,rr,rc,t] = the maximum # of digits that we can consume going from left to
                        right in s by time t, assuming that "L" is at position
                        (lr,lc) and "R" is at position (rr,rc) at time t

Base case:
----------

We'll do an induction on t, the current time step.  The base case is pretty straightforward:

                          [     0         if (lr,lc)=(1,0) and (rr,rc)=(1,1) 
  digits[lr,lc,rr,rc,0] = [
                          [ -infinity     otherwise

The base case simply states that our fingers "L" and "R" must start at the positions indicated
in the problem statement at time 0.

Inductive case:
---------------

For the inductive case, suppose (lr,lc) and (rr,rc) are the current positions of "L" and "R"
respectively.  Let value[r,c] be a character indicating the key at position (r,c).
Furthermore, let S be the set of all positions that "L" and "R" *could have* had
prior to moving to (lr,lc) and (rr,rc) at time t.  How do you compute S?  Simply take (lr,lc),(rr,rc),
consider moving each finger up, down, left, or right (or staying still), and retain only those
positions which are valid (i.e., have coordinates which correspond to a valid key on the numeric
keypad).

Then, we have,                               
                               
digits[lr,lc,rr,rc,t] 

                          [ digits[plr,plc,prr,prc,t-1] +                                                  ]
 =          max           [     (plr==lr && plc == lc && s[digits[plr,plc,prr,prc,t-1]] == value(lr,lc) || ]
   (plr,plc,prr,pcc) in S [      prr==rr && prc == rc && s[digits[plr,plc,prr,prc,t-1]] == value(rr,rc))   ]

The recurrence basically states that the maximum number of digits that can be consumed when ending up in
position (lr,lc),(rr,rc) at time t can be determined by looking at all possible previous positions of the
fingers and adding one if either finger didn't move and could have pressed the next digit in the number.
The only thing that remains is to fill in this table in an order that ensures you don't use any values
before they are computed.  There are a number of ways to implement this and any should work given the
constraints listed in the problem.