After five years, the most high-profile event in motor racing, Formula 1, returns to China. The Chinese Grand Prix was recently held at the Shanghai International Circuit. Formula 1 cars can reach speeds of up to 350 km/h. To ensure the safety of the drivers, the cars must pass rigorous crash tests.

We consider the following simplified version of a crash test. Initially, a car is positioned with its front facing a wall, at a distance of meters from the wall. This crash test provides types of boosters, where the -th type of booster has a thrust performance of , and there are ample quantities of each type of booster. Suppose the current distance between the car's front and the wall is , and we use a booster with a thrust performance of . When , the car will move forward meters and then stop. Otherwise, the car will move forward meters, crash into the wall, and rebound meters, after which it stops, still facing the wall.

Now, you want to know, through any number of operations (including no operation), what the minimum distance between the car's front and the wall can be?

The first line of input contains two positive integers  and  (), denoting the number of boosters and the distance between the Formula 1 car and the wall, respectively.

The second line of inputcontains  positive integers  (), denoting the thrust performance of each booster.

Output an integer in a line, denoting the minimum possible distance between the car's front and the wall.

1 10
3

1

An optimal strategy is .

2 10
3 4

0

An optimal strategy is .

2 1
3 7

0

An optimal strategy is .

10 4306315981482911
4306 3519 8148 2911 9970 7222 5462 1844 7072 1702

0

10 123456789987654321
10 10 10 10 10 10 10 10 10 10

1