#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

// #define Hydro

const int N = 2010;

char cost[N];
int n;

int dfs(int l, int r) {
    static int f[N][N];
    if (l > r) return 0;
    if (f[l][r]) return f[l][r];
    int& res = f[l][r] = 0x3f3f3f3f;
    for (int i = l; i <= r; ++i)
        res = min(res, max(dfs(l, i - 1), dfs(i + 1, r)) + (cost[i] ^ 48));
    return res;
}

signed main() {
    #ifdef Hydro
    freopen("cost.in", "r", stdin);
    freopen("cost.out", "w", stdout);
    #endif
    scanf("%s", cost + 1);
    n = strlen(cost + 1);
    printf("%d", dfs(1, n));
    return 0;
}