### Problem Statement

The game "Barons and Coins" utilizes a customized chess board that can be much larger than the usual 8x8. The game involves the use of a special chess piece, the baron. Initially, a baron is placed on the top-left cell of the board (specified as x=0, y=0) and coins are placed by the other players on specific cells of the board. The objective of the game is to use the baron to capture as many coins as possible. A coin is considered captured when the player moves the baron to the cell where the coin has been placed.

A baron's movement is as follows: In the first turn, the baron moves from its cell (x,y) to cell (x + K1, y + 1) such that K1 is positive. After the first turn, the i-th move is specified as moving from current cell (x,y) to a new cell (x+Ki , y+1) such that Ki is strictly greater than Ki-1 .

The coordinates of every coin are given in the int[] x and the int[] y, where the i-th coin is located on cell (x[i], y[i]). Return the maximum number of coins a player can capture.

### Definition

 Class: BaronsAndCoins Method: getMaximum Parameters: int[], int[] Returns: int Method signature: int getMaximum(int[] x, int[] y) (be sure your method is public)

### Constraints

-x will contain between 1 and 50 elements, inclusive.
-y will contain the same number of elements as x.
-Each element of x will be between 1 and 10000, inclusive.
-Each element of y will be between 1 and 10000, inclusive.
-Each pair x[i], y[i] will be distinct.

### Examples

0)

 `{15, 5, 30}` `{4, 5, 6}`
`Returns: 2`
 The baron can move in this order to obtain the coins at (15,4) and (30,6): (0,0) -> (2,1) -> (5,2) -> (9,3) -> (15,4) -> (22,5) -> (30,6)
1)

 `{10}` `{10}`
`Returns: 0`
 No valid sequence of baron movements can take the baron from (0,0) to (10,10).
2)

 `{1, 3, 6, 10, 15, 21}` `{1, 2, 3, 4, 5, 6}`
`Returns: 6`
3)

 `{5, 10, 15, 20, 25, 30, 35, 40, 45}` `{1, 1, 1, 2, 2, 2, 3, 3, 3}`
`Returns: 3`
4)

 `{1, 3, 6, 10, 22, 35, 50, 66}` `{1, 2, 3, 1, 2, 3, 4, 5}`
`Returns: 5`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13905&pm=10006

vexorian

#### Testers:

PabloGilberto , bmerry , ivan_metelsky

#### Problem categories:

Dynamic Programming, Search