序列构筑 (seq)

题目描述

Y 同学正在研究一种字符串序列的构筑方法。给定 $N$ 个不同的字符串 $s_1, s_2, \dots, s_N$，每个字符串 $s_i$ 都对应一个权值 $p_i$。

Y 同学希望从这些字符串中挑选出若干个，组成一个序列 $t_1, t_2, \dots, t_k$，使得对于序列中任意相邻的两个字符串 $t_j$ 与 $t_{j+1}$ ($1 \le j < k$)，均满足 $t_j$ 是 $t_{j+1}$ 的真前缀。

一个字符串 $A$ 是字符串 $B$ 的真前缀，当且仅当 $A$ 是 $B$ 的前缀且 $A \neq B$。

该序列的权值定义为序列中所有字符串的权值之和，即 $\sum_{j=1}^k \text{weight}(t_j)$。请你帮助 Y 同学计算出能够构筑的序列权值的最大值。

输入格式

第一行包含一个整数 $N$，表示候选字符串的数量。

接下来的 $N$ 行，每行包含一个字符串 $s_i$ 和一个整数 $p_i$，中间用空格隔开。

输出格式

输出一行一个整数，表示序列权值的最大值。

样例

样例输入 #1

7
nefer 1
amun 3
nefertari 10
neferti 2
nefertem 4
nefertiti 9
amunra 10

样例输出 #1

13

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le N \le 10^6$，$\sum \vert s_i \vert \le 10^6$，$1 \le p_i \le 10^9$。所有字符串均由小写英文字母组成，且保证输入的 $N$ 个字符串互不相同。

• 特殊性质 A：所有字符串均仅由小写字母 a 组成。
• 特殊性质 B：保证每个字符串的长度 $\vert s_i \vert \le 5$。