题目描述

有一个长度为 $n$ 的数组（$n$ 是 $10$ 的倍数），每个数 $a_i$ 都是区间 $[0,9]$ 中的整数。小明发现数组里每种数出现的次数不太平均，而更改第 $i$ 个数的代价为 $b_i$，他想更改若干个数的值使得这 $10$ 种数出现的次数相等（都等于 $n/10$），请问代价和最少为多少。

输入格式

输入的第一行包含一个正整数 $n$。

接下来 $n$ 行，第 $i$ 行包含两个整数 $a_i,b_i$，用一个空格分隔。

输出格式

输出一行包含一个正整数表示答案。

10
1 1
1 2
1 3
2 4
2 5
2 6
3 7
3 8
3 9
4 10

27

解释 #1

只更改第 $1,2,4,5,7,8$ 个数，需要花费代价 $1+2+4+5+7+8=27$。

数据范围

• 对于 $20\%$ 的评测用例，$n≤1000$；
• 对于所有评测用例，$n≤100000$, $0<b_i≤2×10^5$。