Ньют в пещере
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ньют Саламандер готовится к решающей схватке с Грин-де-Вальдом в одной из древних пещер. Волшебный чемодан Ньюта истрепался и сейчас находится в ремонте, поэтому Ньюту приходится носить с собой один из чемоданов похуже. Новые чемоданы не такие волшебные, поэтому количество тварей, способных вылезти из чемодана, напрямую зависит от его площади. Чем больше произведение ширины чемодана на высоту, тем больше тварей смогут прийти на помощь Ньюту в сложную минуту. А еще чемодан очень-очень тяжелый.

Пещера представляет с собой матрицу $$$A$$$ из $$$n$$$ строк и $$$m$$$ столбцов. При этом $$$j$$$-й столбец характеризуется двумя целыми значениями: $$$a_j$$$ и $$$b_j$$$. Пусть $$$A_{i, j}$$$ — клетка матрицы, находящаяся на пересечении $$$i$$$-й строки и $$$j$$$-го столбца. Тогда клетки $$$A_{1,j}, A_{2, j}, ..., A_{a_j, j}$$$, а также $$$A_{n, j}, A_{n - 1, j}, ..., A_{n - b_j + 1, j}$$$ являются стенами пещеры, через них нельзя пройти. Иными словами, в $$$j$$$-м столбце стенами являются $$$a_j$$$ верхних клеток и $$$b_j$$$ нижних клеток.

Ньют может тащить свой чемодан по полу пещеры так, что стенки чемодана будут всегда параллельны стенам пещеры. Ньют может войти в пещеру в любой клетке первого столбца. Ему нужно дотащить свой чемодан так, чтобы его правая сторона находилась в последнем столбце. Герой может двигать чемодан вверх, вниз и вправо. В любой момент чемодан не должен пересекать стенки пещеры или выходить за ее границы, иначе Грин-де-Вальд может что-то заподозрить.

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

Входные данные

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$m$$$ — количество строк и столбцов в таблице, характеризующей пещеру $$$(1 \leq n \leq 10^9, 1\leq m \leq 5\,000)$$$.

Вторая строка содержит $$$m$$$ целых чисел $$$a_j$$$.

Третья строка содержит $$$m$$$ целых чисел $$$b_j$$$.

Гарантируется, что $$$0 \leq a_i, b_i \leq 10^9$$$, а также $$$a_i + b_i \leq n$$$.

Выходные данные

Выведите единственное число — наибольшую площадь чемодана, который удастся пронести в глубь пещеры.

Будем считать, что чемодан площадью $$$0$$$ можно пронести в глубь любой пещеры.

Пример

Входные данные
4 7
0 0 0 0 2 2 2
2 2 0 0 0 0 0
Выходные данные
4

Примечание

Тесту из условия соответствует такая пещера:

....###

....###

##.....

##.....

# - стенки пещеры, . - свободные клетки