### Problem Statement

There are N bottles on a shelf (numbered from 1 to N). Some little kids are playing football near the shelf. Sometimes it happens that their ball hits the shelf and every bottle with an index between left[i] and right[i], inclusive, that is also divisible by damage[i] falls on the ground and breaks.

Given N and the arrays left, right and damage. The ball has hit the shelf exactly M times, where M is the size of each of the three arrays. Count and return the number of bottles broken by the kids.

### Definition

 Class: BottlesOnShelf Method: getNumBroken Parameters: int, int[], int[], int[] Returns: int Method signature: int getNumBroken(int N, int[] left, int[] right, int[] damage) (be sure your method is public)

### Constraints

-N will be between 1 and 1,000,000,000, inclusive.
-left, right and damage will each contain between 1 and 18 elements, inclusive.
-left, right and damage will contain the same number of elements.
-Each element of left and right will be between 1 and N, inclusive.
-For each i, left[i] will be less than or equal to right[i].
-Each element of damage will be between 1 and 42, inclusive.

### Examples

0)

 `7` `{1}` `{7}` `{2}`
`Returns: 3`
 Every second bottle has been broken by the kids. The shelf looks like this (.-unbroken, X-broken): ` .X.X.X.`
1)

 `7` `{1,1}` `{7,7}` `{2,3}`
`Returns: 4`
 Every bottle dividible by 2 or 3 has been broken. ` .XXX.X.`
2)

 `7` `{1,1,1}` `{7,7,7}` `{2,3,6}`
`Returns: 4`
 Now every bottle divisible by 6 has been broken also, but the result is the same as in last example. ` .XXX.X.`
3)

 `10` `{1,6}` `{5,10}` `{1,7}`
`Returns: 6`
 From the first half of the shelf, every bottle has been broken. From the second half only the bottle with number 7 has been broken. ` XXXXX.X...`
4)

 `5` `{4}` `{4}` `{7}`
`Returns: 0`
 None bottle has been broken.
5)

 `1000000000` `{1}` `{1000000000}` `{1}`
`Returns: 1000000000`
 Every bottle has been broken.

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14244&pm=11008

Mimino

#### Testers:

Rustyoldman , ivan_metelsky , rng_58 , wrong

#### Problem categories:

Math, Simple Search, Iteration