在 Byteland 有一家商店出售 $n$ 种石英。每天每种石英只有两块在售，且第二块仅在第一块售出后才会上架。

两位巫师 Alice 和 Bob 正在收集这 $n$ 种石英以强化他们的魔杖。由于石英短缺，他们达成协议：每天每人每种石英最多只能购买一块。两人都希望每天最小化各自的成本。为了体现公平，Alice 先买一块石英，然后 Bob 和 Alice 轮流各买两块，直到只剩下一块石英。还没集齐所有种类石英的人购买最后一块。

在接下来的 $m$ 天里，某种石英的两块价格会发生永久性变化。Alice 想知道，如果 Alice 和 Bob 在第一天以及随后的每一天都采取最优策略，她集齐所有种类石英的最小成本是多少。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^5$)，分别表示石英的种类数和后续的天数。

接下来 $n$ 行，第 $i$ 行包含两个整数 $a$ 和 $b$ ($1 \le a, b \le 10^5$)，分别表示第 $i$ 种石英在售的第一块和第二块的价格。

接下来 $m$ 行，每行包含三个整数 $t$ ($1 \le t \le n$)，$x$ 和 $y$ ($1 \le x, y \le 10^5$)，表示第 $t$ 种石英在售的第一块和第二块价格分别变为 $x$ 和 $y$。

输出格式

输出 $m + 1$ 行，每行包含一个整数，分别表示第一天以及随后的每一天 Alice 集齐所有种类石英的最小成本。

样例

输入 1

4 5
2 4
5 7
1 7
2 1
4 5 2
1 6 2
4 4 3
2 1 3
3 6 6

输出 1

13
14
15
14
10
13

说明

在样例中，第一天的一种最优策略如下：

• Alice 购买第三种石英的第一块。
• Bob 购买第一种和第二种石英的第一块。
• Alice 购买第一种和第二种石英的第二块。
• Bob 购买第三种石英的第二块和第四种石英的第一块。
• Alice 购买第四种石英的第二块，这也是最后一块石英。