题目描述

有 $n$ 类装备和 $m$ 种材料。材料 $i$ 当前适配第 $p_i$ 类装备，花费 $c_i$ 可把它改为适配任意另一类。小婷希望适配第 $1$ 类装备的材料种数严格多于任意其他一类，求最小费用。

输入格式

第一行 $n,m$。接下来 $m$ 行为 $p_i,c_i$。

输出格式

输出最小费用。

输入

5 1
1 402053569

输出

0

输入

34 5
1 66903254
19 166135827
14 342004071
5 576999943
14 197379685

输出

197379685

输入

13 6
13 965712299
9 480072454
4 103246364
6 32127805
5 374909756
10 284041923

输出

135374169

数据范围

$1\le n,m\le1000$，$1\le p_i\le n$，$1\le c_i\le10^9$。