ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1191. Catch the thief!

Time limit: 1.0 second
Memory limit: 64 MB
A thief is fleeing a place of crime. A cop follows him, with a time lag of L minutes. They run equally fast, thus the lag between them remains constant. Finally, feeling tired, the thief reaches a tram stop. He wants to take a tram of a specific route; trams follow each other with an interval of exactly K1 minutes on this route at any time of day and night. When the tram comes, the thief boards it. The policeman comes to the same tram stop. If the thief is still there waiting for the tram to arrive, the policeman arrests him. If the thief is gone, the cop himself waits for a tram of the same route. The thief leaves his tram at some stop and starts waiting for a tram of another route (trams of that route keep an interval of exactly K2 minutes). When a tram arrives, the thief gets on it and continues his way. Of course, the cop leaves his tram also at this stop and, if the thief is still there, arrests him. If the thief managed to leave, the policeman waits for a tram of the same route that the thief used and follows the thief…
This process continues until either the policeman arrests the thief or the thief, having used N trams, reaches his secret cover place where he is safe.
Although the speeds of the cop and the thief remain equal all the time and the speeds of their trams are equal, it may happen that the policeman is lucky to overtake the thief. For instance, if L < K1, then it may happen that the policeman reaches the first stop when the thief is still waiting for a tram there. Other situations are also possible. Write a program that determines whether the cop can catch the thief.


The input consists of two lines: in the first line there are the numbers L (0 < L < 100) and N (0 < N < 100) delimited with a space. In the second line there are time intervals K1, K2, …, KN (0 < Ki < 100) between trams of the corresponding routes. These numbers are also separated with spaces. All numbers in the input data are integers.


Output NO if the cop has no chance to overtake the thief before he reaches his cover place; output YES if he still has such a chance.


8 3
6 4 3
15 4
7 3 13 6
Problem Author: Leonid Volkov
Problem Source: Fifth High School Children Programming Contest, Ekaterinburg, March 02, 2002