| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 3 | 0 | 0 | 0.000% |
В парке развлечений <<Пуперленд>> открылся огромный верёвочный парк. Особая гордость парка --- трасса, состоящая из $n$ платформ, соединённых $n-1$-й верёвками: первая платформа соединена со второй, вторая --- с третьей, \ldots, $n-1$-я --- с $n$-й, веревка, соединяющая $i$-ю платформу с $i+1$-й имеет длину $l_i$.
В парке серьёзно относятся к технике безопасности, так что для трассы были разработаны следующие правила эксплуатации:
В день открытия в парк пришло $m$ человек, каждый из которых хочет пройти по трассе. Все они выстраились в очередь на первой платформе и сразу после открытия трассы готовы начать свое приключение. Посетители должны двигаться вдоль трассы в том порядке, в котором они стоят в очереди на первой платформе, меняться местами с другим посетителем во врем прохождения трассы не разрешается. Все посетители должны добраться до $n$-й платформы и покинуть трассу.
Все люди разные и будут проходить трассу с разной скоростью. Для $j$-го посетителя известна скорость $v_{i, j}$ м/c --- максимальная скорость, с которой он может проходить по веревке, соединяющей $i$-ю и $i+1$-ю платформы.
Администрация парка не ожидала такого наплыва посетителей и теперь опасается, что все посетители могут не успеть пройти трассу до закрытия парка. Помогите им посчитать минимальное время, которое потребуется всем посетителям, чтобы пройти трассу.
В первой строке заданы два целых числа $n$ ($2 \le n \le 100$) и $m$ ($1 \le m \le 100$) --- число платформ на трассе и число посетителей.
Во второй строке заданы $n - 2$ целых числа $p_2, \ldots, p_{n-1}$ ($1 \le p_i \le 100$) --- ограничения на число людей на платформах. Обратите внимание, что если $n = 2$, то эта строка пуста.
В следующей строке заданы $n - 1$ целое число $r_1, r_2, \ldots, r_{n-1}$ ($1 \le r_i \le 100$) --- ограничение на число людей на $i$-й верёвке.
В следующей строке заданы $n - 1$ целое число $l_1, l_2, \ldots, r_{n-1}$ ($1 \le l_i \le 100$) --- длины верёвок в метрах.
В следующей строке заданы $n - 1$ целое число $d_1, d_2, \ldots, d_{n-1}$ --- ограничение в метрах на расстояние между людьми на $i$-й верёвке. Гарантируется, что $1 \le d_i \le l_i$.
В оставшихся $n - 1$ строке находится по $m$ целых чисел:
$v_{1, 1}, v_{1, 2}, \ldots, v_{1, m}$ $v_{2, 1}, v_{2, 2}, \ldots, v_{2, m}$ $\dots$ $v_{n-1, 1}, v_{n-1, 2}, \ldots, v_{n-1, m}$,
где $v_{i,j}$ --- скорость в м/с $j$-го посетителя на $i$-й верёвке ($1 \le v_{i, j} \le 100$).
Выведите единственное число: время в секундах которое необходимо, чтобы все посетители прошли трассу.
Ваш ответ должен иметь относительную или абсолютную погрешность не больше $10^{-6}$. Таким образом, он будет засчитан, если $\frac{|a-p|}{\max(a, 1)} \le 10^{-6}$, где $p$ --- ваш ответ, а $a$ --- правильный ответ.
2 1 1 30 2 2
15
3 2 1 2 2 10 10 5 5 2 2 1 2
17.5