A test driver in a car company tests a new prototype. For each test drive, he is given a list of restrictions, limiting his speed at certain moments in time. The test driver wants to reach as fast a speed as possible. You should write a program which will find the maximal speed he can reach without violating the restrictions.
You will be given a String restrictions, giving you the restrictions for the test-drive. Each element of restrictions will contain three integers S, T and D separated by single spaces. The restriction becomes active T seconds after the start of the test-drive and stays active for D seconds. While the restriction is active the car can not go faster than S meters per second. If two or more restrictions are applicable at the same time, the restriction with the minimal speed should be taken into account.
At the start of the test drive, the car is motionless. Given two ints, duration, the total duration of the test drive in seconds, and acceleration, the maximal possible acceleration of the car in meters per second squared, return the maximal speed allowed by the test-drive restrictions. Please note that acceleration applies both to increasing and decreasing speed (braking).
|-||The car does not have to come to a complete stop at the final moment of the test drive. It can still be moving.|
|-||For the purposes of the problem you may assume the car has no speed limit at all.|
|-||Your return value must have an absolute or relative error less than 1e-9.|
|-||restrictions will contain between 0 and 50 elements, inclusive.|
|-||Each element of restrictions will be formatted as "S T D".|
|-||In each element of restrictions, S, T and D will be separated by single spaces and contain no leading zeroes.|
|-||In each element of restrictions, S will be an integer between 0 and 100, inclusive.|
|-||In each element of restrictions, T will be an integer between 0 and duration, inclusive.|
|-||In each element of restrictions, D will be an integer between 0 and 1000, inclusive.|
|-||duration will be between 1 and 1000, inclusive.|
|-||acceleration will be between 1 and 25, inclusive.|