Vasya 和 Petya 正在使用一种有趣的数据存储结构:金字塔。
金字塔由 n 行组成,第 i 行包含 i 个单元格。每行相对于前一行向左移动半个单元格。这些单元格用从 1 到 $$\frac{n(n+1)}{2}$$ 的整数编号,如下图所示。
n = 5 时的金字塔示例如下:
该数据结构可以执行两种类型的操作:
1. 更改特定单元格的值。它由三个整数描述:“t i v”,其中 t = 1(操作类型),i — 要更改的单元格编号,v 是要分配给单元格的值。
2. 更改某些子金字塔的值。该图显示了一个突出显示的子金字塔,其顶部位于单元格 5 中。它由 s + 2 个数字描述:“t i v1 v2 ... vs”,其中 t = 2,i — 金字塔顶部单元格的编号,s — 子金字塔的大小(它具有的单元格数量),vj — 应分配给第 j 个单元格的值亚金字塔的细胞。
形式上:顶部位于第 k 行第 i 个单元格(第 5 个单元格是第三行的第二个单元格)的子金字塔将包含从 k 到 n 行的单元格,第 (k + p) 行包含从第 i 到第 (i + p) 的单元格 (0 ≤ p ≤ n - k)。
Vasya 和 Petya 有两座相同的金字塔。 Vasya 更改了金字塔中的一些单元格,现在他想将更改发送给 Petya。为此,他希望找到一个操作序列,让 Petya 可以重复 Vasya 的所有更改。在所有可能的序列中,瓦西亚必须选择最小的一个(包含最少数字的序列)。
你有一个 n 行的金字塔,其中有 k 个已更改的单元格。找出导致 k 个已更改单元格中的每一个都被至少一个操作更改的操作序列。在所有可能的序列中选择包含最少数字的序列。
输入
第一行包含两个整数 n 和 k (1 ≤ n, k ≤ 105)。
接下来的 k 行包含修改后的单元格 ri 和 ci (1 ≤ ci ≤ ri ≤ n) 的坐标 — 行和行中单元格的编号。所有细胞都是不同的。
输出
打印一个数字,显示最终序列有多少个数字。
示例
输入 #1
4 5 3 1 3 3 4 1 4 3 4 4
输出 #1
10
输入 #2
7 11 2 2 3 1 4 3 5 1 5 2 5 5 6 4 7 2 7 3 7 4 7 5
输出 #2
26
注意
第一个示例的可能解决方案之一包含两个操作:
2 4 v4 v7 v8
2 6 v6 v9 v10
图片显示了更改后的单元格颜色突出显示。第一个操作使用的子金字塔突出显示为蓝色,第一个操作使用的子金字塔突出显示为黄色: