4512. 回文串

【题目描述】

小R 有一个长度为L 的字符串S = s₁ ...s_L，其中只包含小写英文字母。小R 发现，虽然S 可能很长，但它可以分成n 个连续的段，其中第i (1 ≤ i ≤ n) 段由ai 个小写英文字母ci 构成。把这n 段依次拼接起来便得到S，因此L =∑ai。相邻两段中的字符可以相同。

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

小X 想让小R 把S 改成回文串。小R 可以将S 中任意一个位置的字符修改成任意小写英文字母。他想用尽量少的修改满足小X 的要求。你需要帮助小R 求出，他最少需要修改多少个位置的字符，才能将S 改成回文串。

【输入格式】

从文件string.in 中读入数据。

输入的第一行包含一个正整数n。输入的第i + 1 (1 ≤ i ≤ n) 行包含一个正整数ai  和一个小写英文字母ci。

【输出格式】

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

【样例1输入】

3
2 a
2 b
1 c

【样例1输出】

2

【样例1说明】

小R 的字符串S 由3 段构成：第1 段由2 个a 组成，第2 段由2 个b 组成，第3 段由1 个c 组成，依次拼接得到S = aabbc。小R 可以将最后一个字符c 和倒数第二个字符b 都改为a，得到回文串aabaa，共修改2 个位置的字符。可以证明，小R 最少需要修改2 个位置的字符，才能将S 改成回文串。

【样例2输入】

2
2 a
3 a

【样例2输出】

0

【样例2说明】

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

【样例3输入】

6
1000000000 a
1000000000 a
1000000000 a
1000000000 b
1000000000 b
1000000000 b

【样例3输出】

3000000000

【数据规模与约定】

【来源】

在此键入。