B. 回文串 / string
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

小 R 有一个长度为 $$$L$$$ 的字符串 $$$S=s_1\ldots s_L$$$，其中只包含小写英文字母。小 R 发现，虽然 $$$S$$$ 可能很长，但它可以分成 $$$n$$$ 个连续的段，其中第 $$$i\ (1\le i\le n)$$$ 段由 $$$a_i$$$ 个小写英文字母 $$$c_i$$$ 构成。把这 $$$n$$$ 段依次拼接起来便得到 $$$S$$$，因此 $$$L=\sum_{i=1}^{n}a_i$$$。相邻两段中的字符可以相同。

小 X 喜欢回文串。若一个字符串反转后与原字符串相同，就称它是回文串，例如 aba、abba 都是回文串，而 aabbc 不是。也就是说，字符串 $$$S$$$ 是回文串，当且仅当对于所有 $$$i\ (1\le i\le L)$$$，均有 $$$s_i=s_{L+1-i}$$$。

小 X 想让小 R 把 $$$S$$$ 改成回文串。小 R 可以将 $$$S$$$ 中任意一个位置的字符修改成任意小写英文字母。他想用尽量少的修改满足小 X 的要求。

你需要帮助小 R 求出，他最少需要修改多少个位置的字符，才能将 $$$S$$$ 改成回文串。

Input

从标准输入读入数据。

输入的第一行包含一个正整数 $$$n$$$。

输入的第 $$$i+1\ (1\le i\le n)$$$ 行包含一个正整数 $$$a_i$$$ 和一个小写英文字母 $$$c_i$$$。

Output

输出到标准输出。

输出一行一个整数，表示小 R 最少需要修改多少个位置的字符，才能将 $$$S$$$ 改成回文串。

Examples
Input
3
2 a
2 b
1 c
Output
2
Input
2
2 a
3 a
Output
0
Input
6
1000000000 a
1000000000 a
1000000000 a
1000000000 b
1000000000 b
1000000000 b
Output
3000000000
Note

补充样例文件可从原题页面的附件下载：https://www.luogu.com.cn/problem/P17828。

样例 1 解释

小 R 的字符串 $$$S$$$ 由 $$$3$$$ 段构成：第 $$$1$$$ 段由 $$$2$$$ 个 a 组成，第 $$$2$$$ 段由 $$$2$$$ 个 b 组成，第 $$$3$$$ 段由 $$$1$$$ 个 c 组成，依次拼接得到 $$$S=\mathtt{aabbc}$$$。

小 R 可以将最后一个字符 c 和倒数第二个字符 b 都改为 a，得到回文串 aabaa，共修改 $$$2$$$ 个位置的字符。可以证明，小 R 最少需要修改 $$$2$$$ 个位置的字符，才能将 $$$S$$$ 改成回文串。

样例 2 解释

小 R 的字符串 $$$S$$$ 由 $$$2$$$ 段构成：第 $$$1$$$ 段由 $$$2$$$ 个 a 组成，第 $$$2$$$ 段由 $$$3$$$ 个 a 组成，依次拼接得到 $$$S=\mathtt{aaaaa}$$$，则 $$$S$$$ 已经是回文串，不需要修改。

样例 4

见题目目录下的 string/4.in 与 string/4.ans。

该样例满足测试点 $$$10\sim12$$$ 的约束条件。

样例 5

见题目目录下的 string/5.in 与 string/5.ans。

该样例满足测试点 $$$13\sim16$$$ 的约束条件。

样例 6

见题目目录下的 string/6.in 与 string/6.ans。

该样例满足测试点 $$$19\sim21$$$ 的约束条件。

数据范围

对于所有测试数据，均有：

  • $$$1\le n\le 2\times10^5$$$；
  • 对于所有 $$$i\ (1\le i\le n)$$$，均有 $$$1\le a_i\le10^9$$$，且 $$$c_i$$$ 为小写英文字母。
测试点编号$$$n\le$$$$$$\max_{i=1}^{n}a_i\le$$$
$$$1$$$$$$1$$$$$$5$$$
$$$2\sim4$$$$$$2$$$$$$5$$$
$$$5,6$$$$$$10$$$$$$1$$$
$$$7,8$$$$$$10$$$$$$50$$$
$$$9$$$$$$2000$$$$$$1$$$
$$$10\sim12$$$$$$2000$$$$$$50$$$
$$$13\sim16$$$$$$2000$$$$$$10^9$$$
$$$17,18$$$$$$2\times10^5$$$$$$1$$$
$$$19\sim21$$$$$$2\times10^5$$$$$$500$$$
$$$22\sim25$$$$$$2\times10^5$$$$$$10^9$$$

本题满分 100 分。官方测试点共 25 个，每个测试点 4 分，独立计分。展示样例中，与官方测试点完全相同的样例保留原测试点分值；其余样例不计分。