Однажды вогоны захотели построить новую гиперпространственную магистраль в удалённой системе из \(n\) планет. Планета номер \(i\) в этой системе находится на орбите \(a_i\), на одной орбите может находиться несколько планет. К сожалению, все эти планеты мешают строительству и должны быть уничтожены.
У вогонов есть для уничтожения две машины.
- Первая машина за раз может уничтожить любую планету за \(1\) триганский пу.
- Вторая машина за раз может уничтожить все планеты на одной орбите этой системы за \(c\) триганских пу.
Вогоны могут использовать каждую машину сколько угодно раз.
Вогоны очень жадные, поэтому они хотят уничтожить все планеты, затратив при этом минимально возможное количество средств. Помогите им подсчитать минимальную стоимость этого проекта.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — минимальную стоимость уничтожения всех планет.
Примечание
В первом наборе входных данных стоимость использования обеих машин одинакова, поэтому можно всегда пользоваться второй машиной и уничтожить все планеты, находящиеся на орбите \(1\), все планеты, находящиеся на орбите \(2\), все планеты, находящиеся на орбите \(4\), все планеты, находящиеся на орбите \(5\).
Во втором наборе входных данных выгодно с помощью второй машины за \(2\) триганских пу уничтожить все планеты находящиеся на орбите \(2\), затем уничтожить с помощью первой машины оставшиеся две планеты.
В третьем наборе входных данных можно воспользоваться первой машиной дважды или второй один раз.
В четвертом наборе входных данных выгодно два раза воспользоваться первой машиной.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
10 1
2 1 4 5 2 4 5 5 1 2
5 2
3 2 1 2 2
2 2
1 1
2 2
1 2
|
4
4
2
2
|
|
2
|
1
1 100
1
|
1
|