Фермер Джон недавно построил огромный амбар, состоящий из n * n решётки комнат, пронумерованных от (1, 1) до (n, n). Беси, будучи коровой которая боится темноты, хочет включить свет в как можно большем количестве комнат.

Беси начинает в комнате (1, 1) - единственной комнате, в которой изначально был включён свет. В некоторых комнатах она найдёт переключатели, которые могут переключать свет в других комнатах. Например, в комнате (1, 1) может находиться переключатель света в комнате (1, 2). Беси может ходить только в те комнаты, где уже горит свет. И также она может переходить из комнаты (x, y) только в четыре соседние комнаты (x − 1, y), (x + 1, y), (x, y − 1), (x, y + 1) (или, возможно, в меньшее количество комнат, если она находится на границе решётки.

Определите максимальное количество комнат, в которые Беси может включить свет.

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

Первая строка содержит целые числа n (2 ≤ n ≤ 100) и m (1 ≤ m ≤ 20000).

Каждая из следующих m строк описывает один переключатель четырьмя целыми числами x, y, a, b, означающими, что в комнате (x, y) можно переключить свет в комнате (a, b). Несколько переключателей могут находится в любой комнате и несколько переключателей могут переключать свет в любой комнате.

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

Одна строка, задающая максимальное количество комнат, в которых Беси может включить свет.

Пример

Здесь Беси может использовать переключатель в комнате (1, 1), чтобы включить свет в комнатах (1, 2) и (1, 3). Затем она может перейти в комнату (1, 3) и включить свет в комнате (2, 1), где она может включить свет в комнате (2, 2). Переключатель в комнате (2, 3) недоступен для неё, поскольку он находится в комнате, где свет не включён. Поэтому Беси может посетить не более 5 комнат.