U140956 新漂亮国大选

漂亮国是一个“团结”，“民主”的国家。

现在，漂亮国马上要迎来2020年大选，大选要选出一个党派作为国家的执政党。因为漂亮国很“民主”，所以漂亮国有$M$个政党：共和党、民主党、社会党、绿党、红党......现在，你被聘请为漂亮国红党选举总顾问，你事先知道了参与大选的选民的数量为$N$ ，并且，对于每一位选民，你知道他将要选举哪一个政党。你担忧地发现，如果正常选举，你的党派并不会赢。不过，你又发现：每一位选民都会在接受一定数额的漂亮金之后改变他的主意。如果你给第$i$位选民$c_i$数额的漂亮金，他就会选举你希望他选举的红党。 那么，如果红党要赢得这场选举，红党就必须拥有比其它政党都多的选票。你向红党中央递交了你的计划：显然，这需要大量的资金。红党对选举势在必得，但是，他们希望花费的漂亮金尽可能少。 请你再算一下：最少需要多少漂亮金，才能保证红党赢得胜利。

无

无

对于$5\%$的数据，$M=2$。 对于$20\%$的数据，$1\le N,M\le 10$。 对于$40\%$的数据，$1\le N,M\le 100$。 对于$80\%$的数据，$1\le N,M\le 3000$。 对于全部数据：$1\le N,M\le 10^5,1\le p_i\le M,1\le c_i\le 10000$。