e-olymp
Задачи

Дождь

Дождь

prb396Капля дождя падает вертикально вниз с большой высоты на землю. На пути у капли могут встретиться препятствия, которые изменяют ее путь к земле.

Будем рассматривать двумерный вариант (на плоскости) этой задачи. Пусть препятствия – это наклонные непересекающиеся отрезки, а капля имеет точечные размеры. Капля падает вертикально вниз из точки, расположенной выше любого из препятствий. Если капля при падении соприкасается с отрезком-препятствием, то она стекает по отрезку вниз, пока не упадет вертикально вниз с меньшего по высоте конца отрезка.

Напишите программу, которая по координате X0 точки появления капли над землей вычисляет координату X точки соприкосновения капли с землей (Y  =  0).

Входные данные

Во входном файле в первой строке содержатся два целых числа через пробел – координата X0 точки появления капли (0  < X0  <  10000) и количество отрезков-препятствий N (0  ≤ N  ≤  100). Далее следует N строк, каждая из которых содержит четыре разделенные пробелами числа x1 ,  y1,x2,   y2 – координаты левого и правого концов отрезка-препятствия (все числа целые и находятся в диапазоне от 0 до 10000, x1 <  x2, y1  ≠  y2). Отрезки не пересекаются и не соприкасаются.

Выходные данные

В выходной файл вывести одно целое число – координату X точки соприкосновения капли с землей.

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные
30 4
25 35 40 30
1 32 20 30
33 22 50 29
18 10 33 19
Выходные данные
18