Махмуд хочет послать сообщение своему другу Эхабу. Их язык состоит из n слов, пронумерованных с 1 по n. У некоторых слов совпадают значения, поэтому существует k групп слов таких, что у всех слов в одной группе значение одинаковое.
Махмуд знает, что стоимость посылки i-го слова равна ai. Каждое слово в сообщении Махмуд может оставить неизменным или заменить его другим словом с тем же значением. Можете ли вы помочь Махмуду определить минимальную стоимость посылки сообщения?
Стоимость посылки сообщения равна сумме стоимостей отправки всех слов в сообщении.
Выходные данные
Единственная строка вывода должна содержать минимальную стоимость посылки сообщения после замены нескольких (возможно, ни одного) слова другими словами с таким же значением.
Примечание
В первом примере Махмуд должен заменить слово «second» на слово «loser», поскольку оно стоит меньше, и тогда стоимость посылки будет равна 100+1+5+1=107.
Во втором примере Махмуд не должен совершать никаких замен, поэтому стоимость будет равна 100+1+5+10=116.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4 4 i loser am the second 100 1 1 5 10 1 1 1 3 2 2 5 1 4 i am the second
|
107
|
|
2
|
5 4 4 i loser am the second 100 20 1 5 10 1 1 1 3 2 2 5 1 4 i am the second
|
116
|