### Problem Statement

Little Dazdraperma likes drawing a lot. She drew some red points on the plane. The coordinates of these points are given in int[] x and int[] y, where the i-th point is located at (x[i], y[i]). Her friend sells blue squares of different types. A square of type i has sides of length sides[i] and a cost of cost[i] assigned to it. She thinks that her picture will be more attractive if all the red points would be covered by squares (possibly overlapping). She decided that the sides of all the squares must be parallel to either the x or y axis. The point A is considered to be covered by a square if it lies inside it or on its boundary.

Now she wonders what is the smallest amount of money she has to spend to cover all red points with blue squares. Note that there is an unlimited amount of squares of each type and if Dazdraperma wants to buy several squares of the same type, she must pay the corresponding cost for each single square. Return the minimum cost for covering all red points with the given squares.

### Definition

 Class: SquaresCovering Method: minCost Parameters: int[], int[], int[], int[] Returns: int Method signature: int minCost(int[] x, int[] y, int[] cost, int[] sides) (be sure your method is public)

### Constraints

-x will contain between 1 and 16 elements, inclusive.
-y will contain the same number of elements as x.
-Each element of x will be between 0 and 1000000000 (109), inclusive.
-Each element of y will be between 0 and 1000000000 (109), inclusive.
-cost will contain between 1 and 50 elements, inclusive.
-sides will contain the same number of elements as cost.
-Each element of sides will be between 1 and 1000000000 (109), inclusive.
-Each element of cost will be between 1 and 100000000 (108), inclusive.

### Examples

0)

 `{1,100}` `{1,100}` `{3,1}` `{100,1}`
`Returns: 2`
 Here it is better to cover each point with its own square of size 1.
1)

 `{1,100}` `{1,100}` `{1,1}` `{100,1}`
`Returns: 1`
 Here it is better to cover both points with one square of size 100.
2)

 `{0,100,201,300}` `{0,0,1,0}` `{6,100,10}` `{1,100,99}`
`Returns: 22`
 In this test case it is better to cover points 0 and 1 with their own squares of size 1 and points 2 and 3 with one square of size 99.
3)

 `{41,6334,19169,11478,26962,5705,23281,41}` `{18467,26500,15724,29358,24464,28145,16827,18467}` `{292,11943,5437,14605,154,12383,18717,19896,21727,11539,19913,26300,9895,23812,30334,4665,7712,6869,27645,32758}` `{9962,2996,4828,32392,33,293,17422,19719,5448,14772,1870,25668,17036,28704,31323,17674,15142,28254,25548,32663}`
`Returns: 738`
 Note that red points can coincide.
4)

 `{41,6334,9169,1478,6962,5705,3281}` `{8467,6500,5724,9358,4464,8145,6827}` `{92,43,37,15,54,83,17,96,27,39,13,100,95,12,34,65,12,69,45,58}` `{962,996,828,392,903,293,422,719,448,772,870,668,36,704,323,674,142,254,548,663}`
`Returns: 84`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14185&pm=10960

K.A.D.R

#### Testers:

Rustyoldman , ivan_metelsky , mohamedafattah , it4.kp , maksay

#### Problem categories:

Dynamic Programming, Geometry, Search