题目描述

鱼需要定时投喂饲料，但是小 L 没有购买任何饲料。好在鱼商给了小 L 一些优惠，将会定时赠送饲料。

一共有 $n$ 种不同的饲料。在接下来的 $q$ 个时刻中，每个时刻会发生以下两种事件之一：

• 鱼商赠送小 L 共 $y$ 克、种类为 $x$ 的饲料；
• 某条鱼需要投喂 $y$ 克饲料，且该鱼喜爱种类为 $x$ 的饲料。小 L 必须从鱼商已经赠送的饲料中任选 $y$ 克喂鱼，不能自行购买饲料。如果所选饲料中恰有 $z$ 克的种类不为 $x$，则这条鱼会积攒 $z$ 的不满意度。

小 L 希望所有鱼的不满意度总和最小。请计算这个最小值。

保证鱼商赠送的饲料足够喂所有鱼。

输入格式

第一行输入两个正整数 $n,q$。

接下来 $q$ 行，每行输入两个整数 $x,y$：

• 如果 $y>0$，表示鱼商赠送 $y$ 克种类为 $x$ 的饲料；
• 否则，表示一条喜爱种类 $x$ 饲料的鱼需要投喂 $-y$ 克饲料。

输出格式

输出一行一个非负整数，表示不满意度总和的最小值。

样例 1

输入

3 5
1 3
2 5
3 3
1 -5
2 -6

输出

3

样例 2

输入

4 8
1 103
2 -49
2 64
1 -86
4 100
2 -89
4 85
3 -101

输出

239

数据范围

对于所有数据：

$$1\le n,q\le 3\times 10^6, \qquad 1\le x\le n, \qquad -3\times 10^{15}\le y\le 10^9.$$

子任务编号	$n\le$	$q\le$	分值
1	$2$	$10^6$	10
2	$200$	$500$	15
3	$30$	$10^5$
4	$10^5$		30
5	$3\times 10^6$