Morning Traffic Lights

Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 256M

Problem type
Allowed languages
C, C++, Haskell, Java, Python

Finally, semester two is starting and you are keen to get to the library to study! You decide to drive to campus but you hate getting stuck in traffic.

Your route is \(D\) kilometres with \(N\) traffic lights. Each light is either red or green (at least as far as you are concerned). You may pass through a green light but not a red light. Amazingly, when you leave home all the lights are red. Each light will turn green for the first time after \(a\) minutes. Then, the light will remain green for \(g\) minutes, turn to red, then remain red for \(r\) minutes and then cycles back to green for \(g\) minutes and so on indefinitely. These values usually differ for each light.

If you arrive at a traffic light the moment it changes colour, assume you make it through.

Your vehicle travels at one kilometre per minute so it also takes \(D\) minutes to get to campus. Determine whether or not you will be stopped at any lights along the way.

Input Specification

The first line contains two integers \(N (1 \leq N \leq 1000)\) and \(D (2 \leq D \leq 10^9)\).

The next \(N\) lines describe a traffic light. Each of these lines contain four integers, \(x (1\leq x < D)\), the location of this light in kilometres, \(a (1 \leq a \leq 10^9)\), the number of minutes after leaving this light will first turn green, \(g (1 \leq g \leq 10^9)\), the number of minutes the light stays green at a time and \(r (1 \leq r \leq 10^9)\), the number of minutes the light stays red in each cycle. No two traffic lights occupy the same location.

Output Specification

If you get to campus without stopping print "YES", else print "NO".

Sample Input 1

1 10
5 3 3 3

Sample Output 1


Sample Input 2

2 10
3 2 10 10
6 2 3 2

Sample Output 2


Sample Input 3

1 10
2 5 1 1

Sample Output 3



There are no comments at the moment.