За карточным столом сидят \(n\) игроков. У каждого из них есть свое любимое число. Любимое число \(j\)-го игрока равно \(f_j\).
На столе перед игроками лежит \(k \cdot n\) карт, на карте с номером \(i\) записано число \(c_i\). Также известен массив \(h_1, h_2, \dots, h_k\), смысл которого будет объяснён ниже.
Игроки должны каким-то образом разобрать все карты так, чтобы каждому из них досталось ровно \(k\) карт. После того, как игроки разберут все карты, каждый из них подсчитает количество своих карт, на которых записано его любимое число. Радость игрока составит \(h_t\), где \(t\) — количество карт игрока, содержащих его любимое число. Если ни одна карта игрока не содержит его любимое число (то есть его \(t=0\)), то радость игрока равна \(0\).
Выведите возможную максимальную суммарную радость игроков после раздачи всех карт. Обратите внимание, что задана одна последовательность \(h_1, \dots, h_k\) на всех игроков.
Выходные данные
Выведите одно целое число — максимальную суммарную радость всех игроков после оптимальной раздачи карт.
Примечание
В первом тестовом примере выгоднее всего распределить карты следующим образом:
- Игрок номер \(1\) получает карты с числами \([1, 3, 8]\);
- Игрок номер \(2\) получает карты с числами \([2, 2, 8]\);
- Игрок номер \(3\) получает карты с числами \([2, 2, 8]\);
- Игрок номер \(4\) получает карты с числами \([5, 5, 5]\).
Таким образом, ответ будет равен \(2 + 6 + 6 + 7 = 21\).
Во втором тестовом примере никто не получит ни одной карты с любимым числом, поэтому ответ равен \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
1 3 2 8 5 5 8 2 2 8 5 2
1 2 2 5
2 6 7
|
21
|
|
2
|
3 3
9 9 9 9 9 9 9 9 9
1 2 3
1 2 3
|
0
|