28821번 - Ньют в пещере 다국어

문제

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

Пещера представляет с собой матрицу $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ドル$ можно пронести в глубь любой пещеры.

제한

노트

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

....###
....###
##.....
##.....

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