D. Передача пирамиды
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вася с Петей используют интересную структуру для хранения данных, пирамиду.

Пирамида состоит из n рядов, в i-том из них содержится i ячеек. Каждый ряд сдвинут относительно предыдущего на половину длины ячейки влево. Ячейки пирамиды пронумерованы от 1 до так, как показано на рисунке ниже.

Пример пирамиды при n = 5:

Эта структура данных умеет выполнять операции двух видов:

  1. Изменить значение конкретной ячейки. Описывается тремя числами: "tiv", где t = 1 (тип операции), i — номер ячейки, которую нужно изменять и v — значение, которое нужно в нее записать.
  2. Изменить значение в некоторой подпирамиде, на изображении выделена подпирамида с вершиной в 5 ячейке. Описывается s + 2 числами: "tiv1v2 ... vs", где t = 2, i — номер ячейки, которая является вершиной подпирамиды, s — размер подпирамиды (количество ячеек в ней), vj — значение, которое необходимо присвоить j-той ячейке подпирамиды.

Формально: подпирамида с вершиной в i-той ячейке k-того ряда (5 ячейка = вторая ячейка третьего ряда) будет содержать ячейки из рядов от k до n, в (k + p)-том из них — ячейки ряда от i-той до (i + p)-той (0 ≤ p ≤ n - k).

У Васи и Пети было две одинаковые пирамиды. Вася в своей пирамиде изменил некоторые ячейки и теперь хочет передать изменения Пете. Для этого он хочет найти последовательность операций, при помощи которой можно повторить все сделанные им изменения, однако, среди всех возможных последовательностей необходимо выбрать самую короткую (содержащую минимальное количество чисел).

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

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

В первой строке содержится два целых числа n и k (1 ≤ n, k ≤ 105).

Следующие k строк содержат координаты измененных ячеек ri и ci (1 ≤ ci ≤ ri ≤ n) — ряд и номер ячейки в ряду. Все ячейки различны.

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

Выведите единственное число — количество чисел в найденной последовательности.

Примеры
Входные данные
4 5
3 1
3 3
4 1
4 3
4 4
Выходные данные
10
Входные данные
7 11
2 2
3 1
4 3
5 1
5 2
5 5
6 4
7 2
7 3
7 4
7 5
Выходные данные
26
Примечание

Одно из возможных решений первого примера состоит из двух операций:

2 4 v4v7v8

2 6 v6v9v10

На изображении измененные ячейки выделены другим цветом, голубым цветом выделена подпирамида, используемая первой операцией, желтым — второй: