В парке развлечений «Пуперленд» открылся огромный верёвочный парк. Особая гордость парка — трасса, состоящая из \(n\) платформ, соединённых \(n − 1\) верёвками: первая платформа соединена
со второй, вторая — с третьей, \(\dots\) , \(n − 1\)-я — с \(n\)-й, верёвка, соединяющая \(i\)-ю платформу с \(i + 1\)-й
имеет длину \(l_i\)
.
В парке серьёзно относятся к технике безопасности, так что для трассы были разработаны следующие правила эксплуатации:
- для всех \(i\) от \(2\) до \(n − 1\) на \(i\)-й платформе разрешается находиться не более, чем \(p_i\) людям одновременно; (первая и последняя платформы достаточно надёжны, и на них может находиться
произвольное число людей);
- на верёвке, протянутой между \(i\)-й и \(i + 1\)-й платформами, разрешается находиться не более,
чем \(r_i\) людям одновременно;
- для каждой верёвки известно минимальное безопасное расстояние \(d_i\) метров, такое что двум
людям, одновременно идущим по этой верёвке, нельзя приближаться друг к другу ближе, чем
на это расстояние.
В день открытия в парк пришло m человек, каждый из которых хочет пройти по трассе. Все
они выстроились в очередь на первой платформе и сразу после открытия трассы готовы начать
свое приключение. Посетители должны двигаться вдоль трассы в том порядке, в котором они стоят
в очереди на первой платформе, меняться местами с другим посетителем во время прохождения
трассы не разрешается. Все посетители должны добраться до \(n\)-й платформы и покинуть трассу.
Все люди разные и будут проходить трассу с разной скоростью. Пронумеруем посетителей от 1
до \(m\) в том порядке, в котором они выстроились в очередь. Для \(j\)-го посетителя известна скорость
\(v_{i,j}\) м/c — максимальная скорость, с которой он может проходить по верёвке, соединяющей \(i\)-ю и
\(i + 1\)-ю платформы. Таким образом, \(j\)-й посетитель может перемещаться по \(i\)-й верёвке с любой скоростью от 0 до \(v_{i,j}\) , соблюдая при этом условия про минимальное расстояние до других посетителей,
идущих по той же верёвке.
Администрация парка не ожидала такого наплыва посетителей и теперь опасается, что все посетители могут не успеть пройти трассу до закрытия парка. Помогите им посчитать минимальное
время, которое потребуется всем посетителям, чтобы пройти трассу
Входные данные
В первой строке заданы два целых числа \(n (2 \le n \le 100)\) и \(m (1 \le m \le 100)\) — число платформ
на трассе и число посетителей.
Во второй строке заданы \(n − 2\) целых числа \(p_2, \dots , p_{n−1} (1 \le p_i \le 100)\) — ограничения на число
людей на платформах. Обратите внимание, что если \(n = 2\), то эта строка пуста.
В следующей строке задано \(n − 1\) целое число \(r_1, r_2, \dots , r_{n−1} (1 \le r_i \le 100)\) — ограничение на
число людей на \(i\)-й верёвке.
В следующей строке задано \(n − 1\) целое число \(l_1, l_2, \dots , l_{n−1} (1 \le l_i \le 100)\) — длины верёвок в
метрах.
В следующей строке задано \(n − 1\) целое число \(d_1, d_2, \dots , d_{n−1}\) — ограничение в метрах на расстояние между людьми на \(i\)-й верёвке. Гарантируется, что \(1 \le d_i \le l_i\).
В оставшихся \(n − 1\) строке находится по \(m\) целых чисел:
\(\)v_{1,1}, v_{1,2}, \dots , v_{1,m}\(\)
\(\)v_{2,1}, v_{2,2}, \dots , v_{2,m}\(\)
\(\)\dots\(\)
\(\)v_{n−1,1}, v_{n−1,2}, \dots , v_{n−1,m},\(\)
где \(v_{i,j}\) — скорость в м/с \(j\)-го посетителя на \(i\)-й верёвке (\(1 \le v_{i,j} \le 100\)).
Выходные данные
Выведите единственное число — время в секундах, которое необходимо, чтобы все посетители
прошли трассу
Ваш ответ должен иметь относительную или абсолютную погрешность не больше \(10^{−6}\).
Таким
образом, он будет засчитан, если \(|a−p|/max(a,1) \le 10^{−6}\)
, где \(p\) — ваш ответ, а \(a\) — правильный ответ