402352: GYM100735 G LCS Revised

Memory Limit：64 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

G. LCS Revisedtime limit per test2 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard output

The longest common subsequence is a well known DP problem: given two strings A and B, one has to compute the maximum length of a subsequence that's common to both A and B.

In this particular problem we work with strings A and B formed only by 0 and 1, having the same length. You're given a string A of length n. Iterate all strings B possible. There are 2n of them. Calculate, for each string B, the longest common subsequence of A and B. Then, output the minimum length obtained.

Input

The first and the only line of the input contains string A, formed only by 0 and 1. It's guaranteed that the length is between 1 and 105.

Output

Output a single number - the requested length.

ExamplesInput
101010
Output
3

Source/Category

加入题单

上一题 下一题 算法标签：