Дан алфавит из n букв, нужно составить строку максимальной длины так, чтобы выполнялись два условия:
- i-я буква встречалась в строке не больше ai раз;
- количество вхождений в строку каждой из букв должно быть различным для всех букв, которые встретились в строке хотя бы один раз.
Выходные данные
Выведите одно целое число — максимальную длину строки, удовлетворяющей требованиям.
Примечание
Для удобства возьмём алфавит из трёх букв: «a», «b», «c». В первом тесте из условия, примерами подходящих строк являются: «cccaabbccbb», «aabcbcbcbcb». Во втором тесте из условия примерами подходящих строк являются: «acc», «cbc».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 5 5
|
11
|
|
2
|
3
1 1 2
|
3
|