[Wannafly冬令营2018Day1]夺宝奇兵(困难版)

内存限制：256 MB 时间限制：1000 ms

$wls$所在的王国有$n$个居民（不包括$wls$），他们共有$m$件神奇的宝物。

对于第$i$件宝物，$wls$可以花费$a_i$的金币把它从原来的主人那里买过来。

请问$wls$最少要准备多少金币，才能使他成为宝物最多的人（$wls$的宝物件数严格比其他所有人多）？

第一行两个整数$n$，$m$。

接下来$m$行，每行两个整数$a_i$, $c_i$，表示第$i$件宝物属于居民$c_i$，$wls$可以花费$a_i$的代价得到它。

$1 \leq n, m \leq 100000$

$1 \leq a_i \leq 1000000000$

$1 \leq c_i \leq n$

一行一个整数表示答案。

C1920 [Wannafly冬令营2018Day1]夺宝奇兵(困难版)