FroggerAndNets

Frogger is a frog who really wants to survive. He also likes to jump.

There is a river. The river is polluted and jumping into it kills Frogger immediately.

In one place there is a ford across the river. At the ford the river is N steps wide. The ford is described by the N-character String stones. The characters of stones are numbered from 0 to N-1. Each character is either '=' (representing river) or 'O' (uppercase oh, representing a stone). The index of each 'O' character is the coordinate of the corresponding stone.

Frogger can stand on the stones. He's an excellent jumper: he can get from any stone to any other stone in a single jump.

Some bad people with nets are trying to catch Frogger. These bad people are afraid to enter the ford, so they remain on the banks of the river.

There will be a sequence exactly C catching attempts. These are numbered from 0 to C-1. Each catching attempt i has two parameters L[i] and R[i] with the following meaning: if Frogger's coordinate is strictly less than L[i] or strictly greater than R[i], he gets tangled into the nets. The bad people will then cook and eat him.

Frogger has observed the bad people's strategy and so he knows all the values L[i] and R[i] in advance.

Frogger can choose any of the stones as his starting location. Once he does so, catching attempt 0 takes place.

Between any two consecutive catching attempts is enough time for Frogger to make exactly one leap. (Remember that he can jump to any other stone. He is also allowed not to jump and simply remain on the same stone.) The length of a jump is the positive difference between the coordinates of the stones where it starts and ends.

Frogger's primary goal is to survive all catching attempts. If he cannot reach this goal, return -1.

Frogger's secondary goal is to jump as much as possible. If he can survive, return the maximum total length of his (at most) C-1 jumps.

In order to keep the input size small, the arrays L and R are generated pseudorandomly, so that each interval L[i], R[i] has width at least minW. Please use the following pseudocode.

state = seed
N     = length(stones)
maxW  = N-1

for i = 0 to C-1:
    state = (state * 1103515245 + 12345) modulo 2^31
    w = minW + (state modulo (maxW - minW + 1))
    state = (state * 1103515245 + 12345) modulo 2^31
    L[i] = state modulo (N - w)
    R[i] = L[i] + w