After decoding the message The Plumbers have sent to them, Ben and Gwen finds out that there is an evil Osmosian named Aggregor who have captured five aliens from the Andromeda Galaxy. His plan is to absorb the powers of these five aliens in order to claim the “ultimate prize”.
Ben and Gwen decides that they need to get these aliens out of their jail cell before Aggregor captures them, but to break them out of the high-security jail cell is harder than they thought it would be.
They analysed the long corridor from the jail cell and realizes that they are guarded with lasers. However, these lasers have certain timings in which they on and off. Each laser is on for x minutes, and then turned off for 1 minute, and then turned on for x minutes and this repeats in a cycle. The number of minutes varies between different lasers.
Also, they realized that it takes exactly 1 minute to walk past a laser. This means that one has to time his escape perfectly and cannot wait until all the lasers are deactivated and then make a run for it. At the first minute (when time is at 0 minutes), the lasers have just been activated and are on.
To make things worse, Aggregor’s guards come at every y-minute interval. This means that Aggregor’s guards will come when the time is at 0 minutes, then at y minutes, then at 2y minutes and so on. During the minute that Aggregor’s guards come, you must not be halfway making your escape as the guards will see you and stop you immediately.
The first line of input consists of two integers, the number of lasers in the corridor, n and the interval k in which the guards come.
The next line of input consists of n integers representing the on-period of each laser. Assume that the prison cell starts before the left-most laser and the exit door is after the right-most laser. Output the earliest time the prisoners can escape from Aggregor’s cruel prison. They can never escape from Aggregor's prison after 1000 minutes as he would already have captured the aliens. If they can never escape Aggregor’s prison, output -1.
Sample Input
2 4
1 6
Explanation
There are 2 lasers in the corridor, the left-most with an on-period of 1 minute and the right-most with an on-period of 6 minutes. The guard comes every four minute interval (when time = 0, time = 4, time = 8, etc)
Sample Output
7
Explanation
At time = 0, both lasers are on and the guard is doing his check. At time = 1, the first laser turns off. At time = 2, both lasers are on. At time = 3, the first laser turns off. At time = 4, both lasers are on and the guard is doing his check. At time = 5, the first lasers turns off. This is the earliest time the prisoners can start making their way out. At time = 6, the first laser turns on and the second laser turns off. The prisoners are at the second laser when it’s off. They reach the exit door and escape the prison at time = 7. (Do note that when you escape at time = 7, you cannot be caught by the guard even if he is doing his patrol at time = 7)