该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

tjpu小镇最近展开一场镇长的竞选，镇上除你之外有n个村民，他们身上共有m张选票，现在你要想办法通过肮脏的手段(啊,万恶的金钱啊！)来获取其他村民的选票，确保你自己身上的选票严格高于所有其他村民的选票。对于第i张选票，你可以花ai的价钱从村民那买过来。虽然你是一个土豪，但是你并不想有无用的花费，所以你希望用最少的金钱来使得自己获选，请问你应该如何py交易，才能花最少的金钱获选，输出最小花费。

输入格式

第一行输入两个数n，m(1<=n<=1000,1<=m<=2000)

接下来m行，每行两个整数ai,bi(1<=ai<=1e9,1<=bi<=n)

表示第i张选票属于村民bi，你可以花费ai来得到它。

输出格式

输出一个数表示最小花费

样例

4 11
10 1
1 1
10 2
1 2
10 3
1 3
15 4
15 4
15 4
15 4
15 4

28