题目描述

有一个长度为 $n$ 的序列 $a$，初始时对于每个位置 $i$（$1 \leq i \leq n$），$a[i] = \lfloor \sqrt{i} \rfloor$，即 $i$ 的平方根向下取整。

接下来有 $q$ 次操作，每次操作给出两个整数 $x, y$，表示将序列中第 $x$ 个元素的值修改为 $y$。

在所有操作执行完毕后，你需要计算整个序列所有元素的和。

数据范围:

对于 $60$%的数据： $1≤n≤10^3,1≤q≤10^3,1≤x≤n,1≤y≤10^6$。

对于 $100$%的数据： $1≤n≤10^{10},1≤q≤10^5,1≤x≤n,1≤y≤10^6$。

输入格式

第一行包含两个整数 $n,q$，分别表示序列长度和操作次数

接下来 $q$ 行，每行两个整数 $x,y$，表示将 $a_x$ 修改成 $y$

输出格式

输出一个整数，表示修改之后所有序列的和。

10 3
2 4
3 5
10 7

30

10000000000 2
1 10
1 2

666661666750001

提示

样例数据1解释

$n=10$，并且 $a[i] = \lfloor \sqrt{i} \rfloor$；

所以原序列为：$[1,1,1,2,2,2,2,2,3,3]$；

修改完成后为：$[1,4,5,2,2,2,2,2,3,7]$，总和为 $30$。