### Problem Statement

Alice and Bob are playing a game called "Naval Battle". The playing field is a row of fieldLength 1x1 squares. At the beginning of the game, Alice placed one or more battleships on the field. Each battleship occupies exactly shipLength consecutive squares. There must be one or more vacant squares between every pair of adjacent battleships. Bob doesn't know how many battleships Alice has placed, and he doesn't know their positions.

Now, Bob starts shooting. For each shot, he says the number of a single square. The squares are numbered from left to right starting with 0. After each shot, Alice tells him if he hit a square that contains a battleship or if he missed.

Bob suspects that Alice is playing dishonestly and providing wrong answers. You are given a int[] shots, the i-th element of which is the number chosen by Bob on his i-th shot. You are also given a String answers, the i-th character of which is '0' (zero) if Alice tells him that he missed on the i-th shot, or '1' (one) if she tells him that he hit a battleship.

Return the 0-based index of the earliest answer after which Bob can be sure that Alice is playing dishonestly. Return -1 if there is no such move.

### Definition

 Class: NavalBattle Method: firstDishonestMove Parameters: int, int, int[], String Returns: int Method signature: int firstDishonestMove(int fieldLength, int shipLength, int[] shots, String answers) (be sure your method is public)

### Constraints

-fieldLength will be between 1 and 50, inclusive.
-shipLength will be between 1 and fieldLength, inclusive.
-shots will contain between 1 and 50 elements, inclusive.
-Each element of shots will be between 0 and fieldLength-1, inclusive.
-answers will contain exactly n characters, where n is the number of elements in shots.
-answers will contain only the digits '0' and '1'.

### Examples

0)

 `1` `1` `{0}` `"1"`
`Returns: -1`
1)

 `3` `2` `{0, 2, 1}` `"110"`
`Returns: 1`
2)

 `5` `2` `{0, 4, 1, 3, 2}` `"11110"`
`Returns: -1`
3)

 `10` `1` `{4, 7, 8, 2}` `"0110"`
`Returns: 2`
 Alice can?t place two battleships without one or more vacant squares between them.
4)

 `10` `10` `{4, 2}` `"01"`
`Returns: 0`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7520

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10742&pm=7520

Mike Mirzayanov

#### Testers:

PabloGilberto , brett1479 , legakis , Olexiy

#### Problem categories:

Dynamic Programming