Задача D. Воздушный замок

Автор:И. Туфанов, И. Олейников   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Накануне нового года Дед Мороз занимается свим привычным делом: он строит воздушные замки. Пространство в котором Дед Мороз строит замки - это куб, который состоит из NxNxN маленьких кубиков. Каждый маленький кубик может быть занят облаком или не занят. Воздушный замок Деда Мороза - это прямоугольный паралеллепипед с целочисленными координатами, стороны которого параллельны осям координат. Кроме того, в пространсте есть M облаков. Дед Мороз не хочет, чтобы его замок задевал облака. Замок задевает облако, если они имеют общую клетку.

Помогите Деду Морозу постоить наибольший по объему замок.

Формат входного файла

Во входном файле содержатся числа N и M. За ними следуют M троек чисел - координаты облаков. Все координаты находятся в пределах между 1 и N включительно. Облака могут занимать одну и ту же клетку.

Формат выходного файла

В выходном файле должно содержаться единственное число - объем самого просторного замка.

Ограничения

1 ≤ N ≤ 80 0 ≤ M ≤ 200000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2 1
1 1 2
4
2
3 0
27

0.135s 0.019s 15