#include <bits/stdc++.h>
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wc++11-extensions"
#pragma GCC diagnostic ignored "-Wunused-const-variable"
using namespace std;
long long max(vector<long long>& a) {
  long long Max = a[0];
  for (long long i = 1; i < a.size(); i++) Max = max(Max, a[i]);
  return Max;
}
long long min(vector<long long>& a) {
  long long Min = a[0];
  for (long long i = 1; i < a.size(); i++) Min = min(Min, a[i]);
  return Min;
}
long long min(long long a, long long b) { return (a < b) ? a : b; }
long long max(long long a, long long b) { return (a > b) ? a : b; }
void debug(vector<long long>& v) {
  for (long long i = 0; i < v.size(); i++) cout << v[i] << ' ';
  cout << endl;
}
const long long ALPHABET_SIZE = 26;
struct trieNode {
  trieNode* a[ALPHABET_SIZE];
  bool isEndOfWord;
  long long cnt;
  long long id;
  trieNode(long long _id) {
    isEndOfWord = false;
    for (long long i = 0; i < ALPHABET_SIZE; i++) a[i] = nullptr;
    cnt = 0;
    id = _id;
  }
};
class trie {
  trieNode* root;
  void deleteUtil(trieNode* croot);

 public:
  long long idc;
  trie();
  inline trieNode* getRoot() { return root; }
  void insert(string& key, trieNode* croot);
  bool search(string& key, trieNode* croot);
  ~trie();
};
trie::trie() {
  idc = 0;
  root = new trieNode(idc++);
}
void trie::insert(string& key, trieNode* croot) {
  trieNode* cur = croot;
  for (long long i = 0; i < key.length(); i++) {
    long long ind = key[i] - 'a';
    if (cur->a[ind] == nullptr) cur->a[ind] = new trieNode(idc++);
    cur = cur->a[ind];
  }
  cur->isEndOfWord = true;
  cur->cnt++;
}
bool trie::search(string& key, trieNode* croot) {
  trieNode* cur = croot;
  if (croot == nullptr) return false;
  for (long long i = 0; i < key.length(); i++) {
    long long ind = key[i] - 'a';
    if (cur->a[ind] == nullptr) return false;
    cur = cur->a[ind];
  }
  return (cur != nullptr);
}
void trie::deleteUtil(trieNode* croot) {
  if (croot == nullptr) return;
  for (long long i = 0; i < ALPHABET_SIZE; i++) {
    deleteUtil(croot->a[i]);
  }
  delete croot;
}
trie::~trie() { deleteUtil(this->root); }
trie T;
vector<vector<long long> > par;
const long long logN = 18;
vector<long long> leaves;
map<long long, long long> depth;
map<long long, long long> Count;
void dfs(trieNode* c, long long p, long long d) {
  if (c == nullptr) return;
  long long C = c->id;
  depth[C] = d;
  par[C][0] = p;
  for (long long i = 1; i <= logN; i++) par[C][i] = par[par[C][i - 1]][i - 1];
  long long cnt = 0;
  if (c->isEndOfWord) {
    leaves.push_back(c->id);
    cnt++;
  }
  for (long long i = 0; i < ALPHABET_SIZE; i++) {
    if (c->a[i] != nullptr) {
      dfs(c->a[i], c->id, d + 1);
      cnt += Count[c->a[i]->id];
    }
  }
  Count[C] = cnt;
}
map<long long, priority_queue<long long> > pq;
void f(trieNode* c) {
  long long C = c->id;
  long long Ms = 0, Mpd = -1;
  priority_queue<long long> q;
  pq[c->id] = q;
  for (long long i = 0; i < ALPHABET_SIZE; i++) {
    if (c->a[i] == nullptr) continue;
    f(c->a[i]);
    priority_queue<long long>& q1 = pq[c->a[i]->id];
    while (!q1.empty()) {
      pq[C].push(q1.top() + 1);
      q1.pop();
    }
  }
  if (c->isEndOfWord)
    pq[C].push(1);
  else {
    long long top = pq[C].top();
    pq[C].pop();
    pq[C].push(1);
  }
}
bool cmp(long long a, long long b) {
  if (Count[a] == Count[b]) return depth[a] > depth[b];
  return Count[a] > Count[b];
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long n;
  cin >> n;
  vector<string> s;
  vector<long long> c(logN + 1, 0);
  long long nc = 0;
  for (long long i = 0; i < n; i++) {
    string x;
    cin >> x;
    s.push_back(x);
    T.insert(x, T.getRoot());
    nc += x.length();
  }
  long long ans = 0;
  for (long long i = 0; i < ALPHABET_SIZE; i++) {
    if (T.getRoot()->a[i] == nullptr) continue;
    f(T.getRoot()->a[i]);
    long long id = T.getRoot()->a[i]->id;
    while (pq[T.getRoot()->a[i]->id].size()) {
      ans += pq[id].top();
      pq[id].pop();
    }
  }
  cout << ans << endl;
  return 0;
}
#pragma GCC diagnostic push

### Prompt

Construct a Cpp code solution to the problem outlined:

Arkady's code contains n variables. Each variable has a unique name consisting of lowercase English letters only. One day Arkady decided to shorten his code.

He wants to replace each variable name with its non-empty prefix so that these new names are still unique (however, a new name of some variable can coincide with some old name of another or same variable). Among such possibilities he wants to find the way with the smallest possible total length of the new names.

A string a is a prefix of a string b if you can delete some (possibly none) characters from the end of b and obtain a.

Please find this minimum possible total length of new names.

Input

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of variables.

The next n lines contain variable names, one per line. Each name is non-empty and contains only lowercase English letters. The total length of these strings is not greater than 10^5. The variable names are distinct.

Output

Print a single integer — the minimum possible total length of new variable names.

Examples

Input

3
codeforces
codehorses
code


Output

6


Input

5
abba
abb
ab
aa
aacada


Output

11


Input

3
telegram
digital
resistance


Output

3

Note

In the first example one of the best options is to shorten the names in the given order as "cod", "co", "c".

In the second example we can shorten the last name to "aac" and the first name to "a" without changing the other names.

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wc++11-extensions"
#pragma GCC diagnostic ignored "-Wunused-const-variable"
using namespace std;
long long max(vector<long long>& a) {
  long long Max = a[0];
  for (long long i = 1; i < a.size(); i++) Max = max(Max, a[i]);
  return Max;
}
long long min(vector<long long>& a) {
  long long Min = a[0];
  for (long long i = 1; i < a.size(); i++) Min = min(Min, a[i]);
  return Min;
}
long long min(long long a, long long b) { return (a < b) ? a : b; }
long long max(long long a, long long b) { return (a > b) ? a : b; }
void debug(vector<long long>& v) {
  for (long long i = 0; i < v.size(); i++) cout << v[i] << ' ';
  cout << endl;
}
const long long ALPHABET_SIZE = 26;
struct trieNode {
  trieNode* a[ALPHABET_SIZE];
  bool isEndOfWord;
  long long cnt;
  long long id;
  trieNode(long long _id) {
    isEndOfWord = false;
    for (long long i = 0; i < ALPHABET_SIZE; i++) a[i] = nullptr;
    cnt = 0;
    id = _id;
  }
};
class trie {
  trieNode* root;
  void deleteUtil(trieNode* croot);

 public:
  long long idc;
  trie();
  inline trieNode* getRoot() { return root; }
  void insert(string& key, trieNode* croot);
  bool search(string& key, trieNode* croot);
  ~trie();
};
trie::trie() {
  idc = 0;
  root = new trieNode(idc++);
}
void trie::insert(string& key, trieNode* croot) {
  trieNode* cur = croot;
  for (long long i = 0; i < key.length(); i++) {
    long long ind = key[i] - 'a';
    if (cur->a[ind] == nullptr) cur->a[ind] = new trieNode(idc++);
    cur = cur->a[ind];
  }
  cur->isEndOfWord = true;
  cur->cnt++;
}
bool trie::search(string& key, trieNode* croot) {
  trieNode* cur = croot;
  if (croot == nullptr) return false;
  for (long long i = 0; i < key.length(); i++) {
    long long ind = key[i] - 'a';
    if (cur->a[ind] == nullptr) return false;
    cur = cur->a[ind];
  }
  return (cur != nullptr);
}
void trie::deleteUtil(trieNode* croot) {
  if (croot == nullptr) return;
  for (long long i = 0; i < ALPHABET_SIZE; i++) {
    deleteUtil(croot->a[i]);
  }
  delete croot;
}
trie::~trie() { deleteUtil(this->root); }
trie T;
vector<vector<long long> > par;
const long long logN = 18;
vector<long long> leaves;
map<long long, long long> depth;
map<long long, long long> Count;
void dfs(trieNode* c, long long p, long long d) {
  if (c == nullptr) return;
  long long C = c->id;
  depth[C] = d;
  par[C][0] = p;
  for (long long i = 1; i <= logN; i++) par[C][i] = par[par[C][i - 1]][i - 1];
  long long cnt = 0;
  if (c->isEndOfWord) {
    leaves.push_back(c->id);
    cnt++;
  }
  for (long long i = 0; i < ALPHABET_SIZE; i++) {
    if (c->a[i] != nullptr) {
      dfs(c->a[i], c->id, d + 1);
      cnt += Count[c->a[i]->id];
    }
  }
  Count[C] = cnt;
}
map<long long, priority_queue<long long> > pq;
void f(trieNode* c) {
  long long C = c->id;
  long long Ms = 0, Mpd = -1;
  priority_queue<long long> q;
  pq[c->id] = q;
  for (long long i = 0; i < ALPHABET_SIZE; i++) {
    if (c->a[i] == nullptr) continue;
    f(c->a[i]);
    priority_queue<long long>& q1 = pq[c->a[i]->id];
    while (!q1.empty()) {
      pq[C].push(q1.top() + 1);
      q1.pop();
    }
  }
  if (c->isEndOfWord)
    pq[C].push(1);
  else {
    long long top = pq[C].top();
    pq[C].pop();
    pq[C].push(1);
  }
}
bool cmp(long long a, long long b) {
  if (Count[a] == Count[b]) return depth[a] > depth[b];
  return Count[a] > Count[b];
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long n;
  cin >> n;
  vector<string> s;
  vector<long long> c(logN + 1, 0);
  long long nc = 0;
  for (long long i = 0; i < n; i++) {
    string x;
    cin >> x;
    s.push_back(x);
    T.insert(x, T.getRoot());
    nc += x.length();
  }
  long long ans = 0;
  for (long long i = 0; i < ALPHABET_SIZE; i++) {
    if (T.getRoot()->a[i] == nullptr) continue;
    f(T.getRoot()->a[i]);
    long long id = T.getRoot()->a[i]->id;
    while (pq[T.getRoot()->a[i]->id].size()) {
      ans += pq[id].top();
      pq[id].pop();
    }
  }
  cout << ans << endl;
  return 0;
}
#pragma GCC diagnostic push

```