Similar Problems

0796. Shavkat and thief

Time limit : 1000 ms
Memory limit : 64 mb

A thief is fleeing a place of crime. Shavkat follows him, with a time lag of L minutes. They run equally fast, thus the lag between them remains constant. 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 Shavkat comes to the same tram stop. If the thief is still there waiting for the tram to arrive, the Shavkat arrests him. If the thief is gone, the Shavkat 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 Shavkat leaves his tram also at this stop and, if the thief is still there, arrests him. If the thief managed to leave, the Shavkat waits for a tram of the same route that the thief used and follows the thief…

This process continues until either the Shavkat arrests the thief or the thief, having used N trams, reaches his secret cover place where he is safe.

Although the speeds of the Shavkat and the thief remain equal all the time and the speeds of their trams are equal, it may happen that the Shavkat is lucky to overtake the thief. For instance, if L < K1, then it may happen that the Shavkat 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 Shavkat 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 K1K2, …, 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 Shavkat 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




















Tayyorladi: Ildar Nasurlayev