Non-Palindromic Segmentation

Little Keke is learning string algorithms! A string \(r\) of length \(m\) is called a palindrome if and only if \(r_i = r_{m+1-i}\) holds for all \(1 \le i \le m\). For example, aaabaaa and abba are palindromic strings, but aaabaa is not.

Given a string \(s\), partition it into several non-empty segments such that each segment is not a palindrome, while maximizing the number of segments. Output the maximum number of segments. If no valid partition exists, output \(-1\).

A segment is defined as a string formed by taking a contiguous block of characters from the original string.

Input Note: Since the string \(s\) can be very long, it is given in compressed form as several pairs of a character and an integer. Each pair \(c, len\) means that the character c appears consecutively len times. The actual string \(s\) is obtained by concatenating these segments.

inputFormat

The input begins with an integer \(k\) on the first line, representing the number of segments. Each of the next \(k\) lines contains a character and an integer separated by space, indicating that the character appears consecutively for the given number of times.

For example:

3
 a 3
 b 2
 a 3

represents the string aaabb aaa (spaces added for clarity), i.e. aaabbaaa.

outputFormat

Output a single integer — the maximum number of segments into which the string can be partitioned such that each segment is not a palindrome. If there is no valid partition, output -1.

sample

1
a 3

-1