В городе 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. Дороги пронумерованы в порядке, соответствующем направлению движения. Напомним, что движение на всех дорогах одностороннее.