g5-09065. 收藏卡之王 未做

卡牌游戏里有 $n$ 种流派、$m$ 张收藏卡，第 $i$ 张卡当前属于流派 $p_i$，花 $c_i$ 金币可以把它改成任意流派。

小林最喜欢 $1$ 号流派，他希望最后属于 $1$ 号流派的卡严格多于其他每一种流派。最少要花多少金币？

第一行两个整数 $n,m$。接下来 $m$ 行，每行两个整数 $p_i,c_i$。

一行一个整数：最少花费。

花 $1$ 把第 $3$ 张卡（$(2,1)$）改成 $1$ 号流派，再花 $1$ 把第 $4$ 张卡（$(3,1)$）改成 $1$ 号流派：$1$ 号流派 $3$ 张，$2$ 号、$3$ 号各 $1$ 张，$3>1$ 且 $3>1$，共花 $2$。只花 $1$ 时 $1$ 号流派最多 $2$ 张，而 $3$ 号流派原有 $2$ 张，无法严格超过。

$1\le n,m\le 1000$，$1\le p_i\le n$，$1\le c_i\le 10^9$。