The Unbuildable Fence Problem

Little L has N types of wooden planks for building a fence, with lengths l₁, l₂, …, l_N available in infinite supply. When building a fence, he will concatenate any number of these planks; hence the total fence length is the sum of the chosen planks’ lengths.

However, Little L soon realizes that many fence lengths cannot be obtained by simply summing these planks. To solve this, he allows himself a little extra trick: he can cut any single plank by an integer number of meters, but no more than M meters from each plank. That is, a plank of length l_i can be processed to yield any integer length in the interval \[ l_i - M, \; l_i \] (with the implicit assumption that the resulting length is positive).

For example, if there are two types of planks with lengths 7 and 11 and M = 1, then the actual available plank lengths are {6, 7, 10, 11}.

The cows, not wanting to be confined by any fence during their games, decide to challenge Little L by designing a target fence length that cannot be achieved no matter how he chooses or cuts his planks. However, Little L does not want the fence to be too short so that the impossibility is obvious – he wants the maximum possible fence length that remains unbuildable by any combination and processing of his wooden planks.

Your task is to help Little L find that maximum unbuildable fence length.

Note: It is guaranteed that the wooden planks (after processing) have a greatest common divisor of 1 so that all sufficiently large lengths are buildable.

inputFormat

The first line contains two integers N and M, where N is the number of wooden plank types and M is the maximum integer meters that may be cut off from any plank.

The second line contains N integers: l₁, l₂, …, l_N, representing the original lengths of the planks.

You may assume that each l_i > M, and that the available processed plank lengths (i.e. each integer in [l_i − M, l_i]) together have a greatest common divisor of 1.

outputFormat

Output a single integer – the maximum fence length that cannot be built by any combination of the available (and possibly processed) wooden planks.

sample

2 1
7 11

15