题目描述

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

若一个字符串反转后与原字符串相同，就称它是回文串。例如 aba、abba 是回文串，而 aabbc 不是。

小 R 可以将 $S$ 中任意一个位置的字符修改成任意小写英文字母。请你求出，最少需要修改多少个位置的字符，才能将 $S$ 改成回文串。

输入格式

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

接下来 $n$ 行，第 $i$ 行包含一个正整数 $a_i$ 和一个小写英文字母 $c_i$，表示第 $i$ 段由 $a_i$ 个字符 $c_i$ 构成。

输出格式

输出一行一个整数，表示最少需要修改的字符位置数。

样例

3
2 a
2 b
1 c

2

2
2 a
3 a

0

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

3000000000

数据范围

对于所有测试数据，$1\le n\le 2\times10^5$，$1\le a_i\le10^9$，且 $c_i$ 为小写英文字母。