First of all we may notice that we don't have to consider moves where some of the feet
end on the position **Zero**.

Why is this the case? Suppose the contrary – that in each optimal solution
the dancer had to land some of his feet on the position **Zero**. Take any
optimal solution where this happens the least number of times. Let's take a look
at the first moment when some of his feet landed on **Zero**.
If these feet are never used again, he could put them on numbered positions
instead. Otherwise consider the first moment when one of them is used, i.e.
moved to some other position. But clearly the dancer could have moved it there
sooner instead of moving it to **Zero**. This leads to a contradiction.
(In other words, using the approach above we can convert any optimal solution
to an optimal solution where **Zero** is never used.

We should also decide how to encode the moves and states of the dancer.
The most appealing form is certainly the binary one – we will use
**A**-bit numbers to store bit vectors.
If the dancer has (or is supposed to have) a foot on some position, the
corresponding bit in the number will be one, otherwise it will be 0.
E.g. the state 1100 would mean that the dancer has feet on positions 3 and 4.
Similarly, the move 1001 would mean that the dancer has to stamp on positions 1 and 4.
One more definition: the *distance* between two states is the number
of feet that need to be changed. In our encoding the distance can be computed
easily (it is simply one half of the number of ones in the bitwise xor of the states).

Now back to the main problem. We will use dynamic programming.
We will have a 2D-array **A** telling us the maximum number of moves we can catch
for the given second and the given state of the dancer.

In the 0^{th} second we certainly cannot catch any move, so we will fill the first row
of the array with zeros.
Now assume that for a given **k** we know the maximum number of moves we can catch
for all of the seconds **i** where **i < k** and all of the dancer states in that seconds.
Now suppose that we want to compute the results in the **k**-th second for the state **l**:
**A**[**k**][**l**].
For each possible state **j** of the dancer we compute the distance from **j** to **l**
and thus the time **t _{j}** it takes to jump from

We need to handle a few special cases. If the time at position **j** is negative
(i.e. **k < t _{j}**), the dancer couldn't be in the given position,
so we may ignore this possibility.
If there is required move to perform in the second

The result is the maximum in the last row of the computed table.

There is one slight optimization: we don't have to call a function to compute the distance
between two states every time we need it, because that is quite time consuming.
Therefore we should precompute its values into the 2D-array **D** (so that
**D**[**i**][**j**]=**distance(i, j)**).