На небе находится \(N\) облаков, и все они двигаются, под воздействием ветра, с постоянной скоростью \(v = (v_x, v_y)\). Т.е. для любого вещественного числа \(t \leq 0\) любая точка любого облака с начальными координатами \((x, y)\) переместится в точку (\(x + t \times v_x\), \(y + t \times v_y\)). В нашей модели облака будут задаваться как многоугольники (включающие свою границу), вершины которых изначально имеют целые координаты. Многоугольники не имеют самопересечений и самокасаний. Облака могут пересекаться друг с другом. На земле находится центр управления спутником (расположенный в точке (0, 0)), а ровно над ним, выше облаков, находится спутник. Центр осуществляет постоянный обмен данными со спутником с помощью лазерного луча. Когда на пути лазерного сигнала находится облако, коммуникация невозможна. В начальный момент времени коммуникация со спутником возможна. За время наблюдения может возникнуть несколько моментов, в которые коммуникация со спутником невозможна, когда луч лазера прерывается одним или несколькими облаками. Ваша задача состоит в том, чтобы написать программу, определяющую количество интервалов времени, когда коммуникация была невозможна.

В городе Z в час пик очень оживленное движение. Неправильно выбранный маршрут может на долгое время задержать вас в пути. Вам известно, что схема города представляет собой N горизонтальных и M вертикальных односторонних дорог, образующих прямоугольник N-1 на M-1 километр. На пересечении каждой вертикальной и горизонтальной дороги находится перекресток, на котором можно изменить направление движения. Заметьте, что для изменения направления движения нужно сначала полностью затормозить.
Вы находитесь в точке (1, 1), или другими словами, в левом нижнем углу города. Движение происходит слева направо и снизу вверх. Вам необходимо добраться до точки (N, M) за наименьшее время. Проблема в том, что на каждой дороге свой скоростной режим и максимальное ускорение, которое можно развить, разное для каждой дороги (и равно, соответственно, \(A_i\) км/\(c^2\) для вертикальной дороги с номером i и \(B_j\) км/c2 для горизонтальной дороги с номером j). При этом скорость на дорогах не ограничена. Ускорение и торможение происходит по стандартным физическим законам.
Однако ваше преимущество состоит в том, что вы хорошо знаете город и можете попасть напрямую с перекрестка (i, j) на перекресток (i+1, j+1), в объезд главных дорог (перед этим также нужно полностью затормозить). Время, необходимое для этого, не зависит от номера перекрестка и равно C. Дороги пронумерованы в порядке, соответствующем направлению движения. Напомним, что движение на всех дорогах одностороннее.

В парке растут два очень высоких дерева, на стволе каждого из которых расположены дупла одно под другим на равном расстоянии друг от друга. Однажды N дятлов решили заселить эти дупла. Некоторые из них знакомы и поэтому хотели бы иметь возможность летать друг к другу в гости. Дятлы летают прямолинейно и очень быстро. Чтобы уменьшить вероятность столкновения, они решили селиться по следующему принципу: