시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

В парке развлечений <<Пуперленд>> открылся огромный верёвочный парк. Особая гордость парка --- трасса, состоящая из $n$ платформ, соединённых $n-1$-й верёвками: первая платформа соединена со второй, вторая --- с третьей, \ldots, $n-1$-я --- с $n$-й, веревка, соединяющая $i$-ю платформу с $i+1$-й имеет длину $l_i$.

В парке серьёзно относятся к технике безопасности, так что для трассы были разработаны следующие правила эксплуатации:

  • для всех $i$ от 2 до $n - 1$ на $i$-й платформе разрешается находиться не более, чем $p_i$  людям одновременно; (первая и последняя платформы достаточно надёжны, и на них может находиться произвольное число людей);
  • на верёвке, протянутой между $i$-й и $i+1$-й платформами, разрешается находиться не более, чем $r_i$ людям одновременно;
  • для каждой верёвки известно минимальное безопасное расстояние $d_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$ --- правильный ответ.

예제 입력 1

2 1

1
30
2
2

예제 출력 1

15

예제 입력 2

3 2
1
2 2
10 10
5 5
2 2
1 2

예제 출력 2

17.5