Вам надано \(N\) рядків \(S_1, S_2, \ldots, S_N\), які складаються з цифр від 1 до 9 і символу X.

Ми виберемо перестановку \(P = (P_1, P_2, \ldots, P_N)\) з (\(1, 2, \ldots, N\)) для створення рядка \(T = S_{P_1} + S_{P_2} + \cdots + S_{P_N}\), де + позначає конкатенацію рядків. Тоді ми обчислимо «оцінку» рядка \(T = T_1T_2\ldots T_{|T|}\)(де \(|T|\) позначає довжину \(T\)). Оцінка розраховується за наступними 9 кроками, починаючи з початкової оцінки 0:

• Додайте 1 бал до результату стільки разів, скільки пар цілих чисел (\(i, j\)), щоб \(1 \leq i \lt j \leq |T|\), \(T_i = X\) і \(T_j\) = 1.

• Додайте 2 бали до результату стільки разів, скільки пар цілих чисел (\(i, j\)), щоб \(1 \leq i \lt j \leq |T|\), \(T_i = X\) і \(T_j\) = 2.

• Додайте 3 бали до результату стільки разів, скільки пар цілих чисел (\(i, j\)), щоб \(1 \leq i \lt j \leq |T|\), \(T_i = X\) і \(T_j\) = 3.

...

• Додайте 9 балів до результату стільки разів, скільки пар цілих чисел (\(i, j\)), щоб \(1 \leq i \lt j \leq |T|\), \(T_i = X\) і \(T_j\) = 9.

Знайти максимально можливу оцінку \(T\), коли \(P\) можна вибрати довільно.

Обмеження

• \(2 \leq N \leq 2 \times 10^5\)
• \(N\) — ціле число.
• \(S_i\) це рядок довжиною не менше 1, що складається з цифр від 1 до 9 і символу X.
• Сума довжин \(S_1, S_2, \ldots, S_N\) не більше \(2 \times 10^5\).

Формат вхідних даних

Перший рядок містить ціле число \(N\)

Наступні  \(N\) рядків містять \(S_i\)

Формат вихідних даних

У вихідний потік виведіть відповідь.

Примітка

До прикладу 1: Коли P = (3, 1, 2), ми маємо \(T = S_3 + S_1 + S_2\) = XXX1X359.

Отже, оцінка \(T\) становить \(1 \times 3 + 3 \times 4 + 5 \times 4 + 9 \times 4\) = 71, яка є максимальною.

Приклад вхідних даних

3
1X3
59
XXX

Приклад вихідних даних

71

Приклад вхідних даних

10
X63X395XX
X2XX3X22X
13
3716XXX6
45X
X6XX
9238
281X92
1XX4X4XX6
54X9X711X1

Приклад вихідних даних

3010