题目描述

现有一个长度为 $n$ 序列 $a$，然后给出$k$个操作 $(u,v)$ ：使 $a_u=v$ 。

每次操作后，快速求出修改之后的序列和。

输入描述

输入第一行两个正整数$n,k(3 \leq n \leq 10^6，1 \leq k \leq 10^6)$

接下来一行 $n$ 个正整数，第$i$个数代表 $a_i(1 \leq a_i \leq 10^9)$ 。

接下来 $k$ 行，每行两个整数 $(u,v)(1\le u\le n,1\le v\le 10^9)$ ，表示将索引为 $u$ 的元素修改为 $v$ 。

输出描述

一行一个整数，表示最小次数。

样例

输入

3 1
1 1 4
1 5

输出

10