pub trait Zero: PartialEq + Sized {
    fn zero() -> Self;
    #[inline]
    fn is_zero(&self) -> bool {
        self == &Self::zero()
    }
}
pub trait One: PartialEq + Sized {
    fn one() -> Self;
    #[inline]
    fn is_one(&self) -> bool {
        self == &Self::one()
    }
}
macro_rules !zero_one_impls {($({$Trait :ident $method :ident $($t :ty ) *,$e :expr } ) *) =>{$($(impl $Trait for $t {#[inline ] fn $method () ->Self {$e } } ) *) *} ;}
zero_one_impls !({Zero zero u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128 ,0 } {Zero zero f32 f64 ,0. } {One one u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128 ,1 } {One one f32 f64 ,1. } ) ;
pub trait IterScan: Sized {
    type Output;
    fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output>;
}
pub trait MarkedIterScan: Sized {
    type Output;
    fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output>;
}
#[derive(Debug)]
pub struct Scanner<'a> {
    iter: std::str::SplitAsciiWhitespace<'a>,
}
impl<'a> Scanner<'a> {
    #[inline]
    pub fn new(s: &'a str) -> Self {
        let iter = s.split_ascii_whitespace();
        Self { iter }
    }
    #[inline]
    pub fn scan<T: IterScan>(&mut self) -> <T as IterScan>::Output {
        T::scan(&mut self.iter).unwrap()
    }
    #[inline]
    pub fn mscan<T: MarkedIterScan>(&mut self, marker: T) -> <T as MarkedIterScan>::Output {
        marker.mscan(&mut self.iter).unwrap()
    }
    #[inline]
    pub fn scan_vec<T: IterScan>(&mut self, size: usize) -> Vec<<T as IterScan>::Output> {
        (0..size)
            .map(|_| T::scan(&mut self.iter).unwrap())
            .collect()
    }
    #[inline]
    pub fn scan_chars(&mut self) -> Vec<char> {
        self.iter.next().unwrap().chars().collect::<Vec<char>>()
    }
    #[inline]
    pub fn scan_chars_with(&mut self, base: char) -> Vec<usize> {
        self.iter
            .next()
            .unwrap()
            .chars()
            .map(|c| (c as u8 - base as u8) as usize)
            .collect::<Vec<usize>>()
    }
}
mod scanner_impls {
    use super::*;
    macro_rules !iter_scan_impls {($($t :ty ) *) =>{$(impl IterScan for $t {type Output =Self ;#[inline ] fn scan <'a ,I :Iterator <Item =&'a str >>(iter :&mut I ) ->Option <Self >{iter .next () ?.parse ::<$t >() .ok () } } ) *} ;}
    iter_scan_impls !(char u8 u16 u32 u64 usize i8 i16 i32 i64 isize f32 f64 u128 i128 String ) ;
    macro_rules !iter_scan_tuple_impl {($($T :ident ) *) =>{impl <$($T :IterScan ) ,*>IterScan for ($($T ,) *) {type Output =($(<$T as IterScan >::Output ,) *) ;#[inline ] fn scan <'a ,It :Iterator <Item =&'a str >>(_iter :&mut It ) ->Option <Self ::Output >{Some (($($T ::scan (_iter ) ?,) *) ) } } } ;}
    iter_scan_tuple_impl!();
    iter_scan_tuple_impl!(A);
    iter_scan_tuple_impl !(A B ) ;
    iter_scan_tuple_impl !(A B C ) ;
    iter_scan_tuple_impl !(A B C D ) ;
    iter_scan_tuple_impl !(A B C D E ) ;
    iter_scan_tuple_impl !(A B C D E F ) ;
    iter_scan_tuple_impl !(A B C D E F G ) ;
    iter_scan_tuple_impl !(A B C D E F G H ) ;
    iter_scan_tuple_impl !(A B C D E F G H I ) ;
    iter_scan_tuple_impl !(A B C D E F G H I J ) ;
    iter_scan_tuple_impl !(A B C D E F G H I J K ) ;
    pub struct ScannerIter<'a, 'b, T> {
        inner: &'b mut Scanner<'a>,
        _marker: std::marker::PhantomData<fn() -> T>,
    }
    impl<'a, 'b, T: IterScan> Iterator for ScannerIter<'a, 'b, T> {
        type Item = <T as IterScan>::Output;
        fn next(&mut self) -> Option<Self::Item> {
            T::scan(&mut self.inner.iter)
        }
    }
    impl<'a> Scanner<'a> {
        #[inline]
        pub fn iter<'b, T: IterScan>(&'b mut self) -> ScannerIter<'a, 'b, T> {
            ScannerIter {
                inner: self,
                _marker: std::marker::PhantomData,
            }
        }
    }
}
pub mod marker {
    use super::*;
    pub struct Usize1;
    impl IterScan for Usize1 {
        type Output = usize;
        #[inline]
        fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> {
            usize::scan(iter).map(|x| x.wrapping_sub(1))
        }
    }
    pub struct Isize1;
    impl IterScan for Isize1 {
        type Output = isize;
        #[inline]
        fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> {
            isize::scan(iter).map(|x| x.wrapping_sub(1))
        }
    }
}
#[macro_export]
macro_rules !min {($e :expr ) =>{$e } ;($e :expr ,$($es :expr ) ,+) =>{std ::cmp ::min ($e ,min !($($es ) ,+) ) } ;}
#[macro_export]
macro_rules !chmin {($dst :expr ,$($src :expr ) ,+) =>{{let x =std ::cmp ::min ($dst ,min !($($src ) ,+) ) ;$dst =x ;} } ;}
#[macro_export]
macro_rules !max {($e :expr ) =>{$e } ;($e :expr ,$($es :expr ) ,+) =>{std ::cmp ::max ($e ,max !($($es ) ,+) ) } ;}
#[macro_export]
macro_rules !chmax {($dst :expr ,$($src :expr ) ,+) =>{{let x =std ::cmp ::max ($dst ,max !($($src ) ,+) ) ;$dst =x ;} } ;}
/// binary operaion: $T \circ T \to T$
pub trait Magma {
    /// type of operands: $T$
    type T: Clone + PartialEq;
    /// binary operaion: $\circ$
    fn operate(&self, x: &Self::T, y: &Self::T) -> Self::T;
    #[inline]
    fn reverse_operate(&self, x: &Self::T, y: &Self::T) -> Self::T {
        self.operate(x, y)
    }
}
/// $\forall a,\forall b,\forall c \in T, (a \circ b) \circ c = a \circ (b \circ c)$
pub trait Associative {}
/// associative binary operation
pub trait SemiGroup: Magma + Associative {}
impl<S: Magma + Associative> SemiGroup for S {}
/// $\exists e \in T, \forall a \in T, e \circ a = a \circ e = e$
pub trait Unital: Magma {
    /// identity element: $e$
    fn unit(&self) -> Self::T;
}
/// associative binary operation and an identity element
pub trait Monoid: SemiGroup + Unital {
    /// binary exponentiation: $x^n = x\circ\ddots\circ x$
    fn pow(&self, x: Self::T, n: usize) -> Self::T {
        let mut n = n;
        let mut res = self.unit();
        let mut base = x;
        while n > 0 {
            if n & 1 == 1 {
                res = self.operate(&res, &base);
            }
            base = self.operate(&base, &base);
            n = n >> 1;
        }
        res
    }
}
impl<M: SemiGroup + Unital> Monoid for M {}
/// $\exists e \in T, \forall a \in T, \exists b,c \in T, b \circ a = a \circ c = e$
pub trait Invertible: Magma {
    /// $a$ where $a \circ x = e$
    fn inverse(&self, x: &Self::T) -> Self::T;
}
/// short cut of right inverse binary operation
pub trait RightInvertibleMagma: Magma {
    /// right inverse binary operation: $\cdot \circ (\cdot^{-1})$
    fn rinv_operation(&self, x: &Self::T, y: &Self::T) -> Self::T;
}
/// associative binary operation and an identity element and inverse elements
pub trait Group: Monoid + Invertible {}
impl<G: Monoid + Invertible> Group for G {}
/// $\forall a,\forall b \in T, a \circ b = b \circ a$
pub trait Commutative {}
/// commutative monoid
pub trait AbelianMonoid: Monoid + Commutative {}
impl<M: Monoid + Commutative> AbelianMonoid for M {}
/// commutative group
pub trait AbelianGroup: Group + Commutative {}
impl<G: Group + Commutative> AbelianGroup for G {}
/// $\forall a \in T, a \circ a = a$
pub trait Idempotent {}
/// idempotent monoid
pub trait IdempotentMonoid: Monoid + Idempotent {}
impl<M: Monoid + Idempotent> IdempotentMonoid for M {}
/// binary operation to select smaller element
#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct MinOperation<T: Clone + Ord + MaximumBounded> {
    _marker: std::marker::PhantomData<fn() -> T>,
}
pub trait MaximumBounded {
    fn maximum() -> Self;
}
mod min_operation_impl {
    use super::*;
    macro_rules !impl_maximum_with_max {([$($wh :tt ) *] ,$t :ty ,$max :expr ) =>{impl <$($wh ) *>MaximumBounded for $t {#[inline ] fn maximum () ->Self {$max } } } ;($t :ty ,$max :expr ) =>{impl MaximumBounded for $t {#[inline ] fn maximum () ->Self {$max } } } ;}
    impl_maximum_with_max!(usize, std::usize::MAX);
    impl_maximum_with_max!(u8, std::u8::MAX);
    impl_maximum_with_max!(u16, std::u16::MAX);
    impl_maximum_with_max!(u32, std::u32::MAX);
    impl_maximum_with_max!(u64, std::u64::MAX);
    impl_maximum_with_max!(isize, std::isize::MAX);
    impl_maximum_with_max!(i8, std::i8::MAX);
    impl_maximum_with_max!(i16, std::i16::MAX);
    impl_maximum_with_max!(i32, std::i32::MAX);
    impl_maximum_with_max!(i64, std::i64::MAX);
    macro_rules !impl_maximum_tuple {($($T :ident ) *) =>{impl <$($T :MaximumBounded ) ,*>MaximumBounded for ($($T ,) *) {#[inline ] fn maximum () ->Self {($(<$T as MaximumBounded >::maximum () ,) *) } } } ;}
    impl_maximum_tuple!();
    impl_maximum_tuple!(A);
    impl_maximum_tuple !(A B ) ;
    impl_maximum_tuple !(A B C ) ;
    impl_maximum_tuple !(A B C D ) ;
    impl_maximum_tuple !(A B C D E ) ;
    impl_maximum_tuple !(A B C D E F ) ;
    impl_maximum_tuple !(A B C D E F G ) ;
    impl_maximum_tuple !(A B C D E F G H ) ;
    impl_maximum_tuple !(A B C D E F G H I ) ;
    impl_maximum_tuple !(A B C D E F G H I J ) ;
    impl_maximum_tuple !(A B C D E F G H I J K ) ;
    impl<T: Clone + Ord + MaximumBounded> MinOperation<T> {
        pub fn new() -> Self {
            Self {
                _marker: std::marker::PhantomData,
            }
        }
    }
    impl<T: Clone + Ord + MaximumBounded> Magma for MinOperation<T> {
        type T = T;
        #[inline]
        fn operate(&self, x: &Self::T, y: &Self::T) -> Self::T {
            std::cmp::min(x, y).clone()
        }
    }
    impl<T: Clone + Ord + MaximumBounded> Unital for MinOperation<T> {
        #[inline]
        fn unit(&self) -> Self::T {
            MaximumBounded::maximum()
        }
    }
    impl<T: Clone + Ord + MaximumBounded> Associative for MinOperation<T> {}
    impl<T: Clone + Ord + MaximumBounded> Commutative for MinOperation<T> {}
    impl<T: Clone + Ord + MaximumBounded> Idempotent for MinOperation<T> {}
}
pub trait Automaton {
    type Alphabet;
    type State;
    type Effect;
    fn initial(&self) -> Self::State;
    fn next(
        &self,
        state: &Self::State,
        alph: &Self::Alphabet,
    ) -> Option<(Self::State, Self::Effect)>;
    fn accept(&self, state: &Self::State) -> bool;
}
pub fn automaton_dp<A, M>(
    dfa: A,
    sigma: impl Iterator<Item = A::Alphabet> + Clone,
    len: usize,
    monoid: M,
    mul: impl Fn(&M::T, &A::Effect) -> M::T,
    init: M::T,
) -> M::T
where
    A: Automaton,
    A::State: Eq + std::hash::Hash,
    M: Monoid,
{
    let mut dp = std::collections::HashMap::new();
    let mut ndp = std::collections::HashMap::new();
    dp.insert(dfa.initial(), init);
    for _ in 0..len {
        for (state, value) in dp.drain() {
            for alph in sigma.clone() {
                if let Some((nstate, eff)) = dfa.next(&state, &alph) {
                    let nvalue = mul(&value, &eff);
                    ndp.entry(nstate)
                        .and_modify(|acc| *acc = monoid.operate(acc, &nvalue))
                        .or_insert(nvalue);
                }
            }
        }
        std::mem::swap(&mut dp, &mut ndp);
        ndp.clear();
    }
    let mut acc = monoid.unit();
    for (state, value) in dp.into_iter() {
        if dfa.accept(&state) {
            acc = monoid.operate(&acc, &value);
        }
    }
    acc
}
pub struct IntersectionAutomaton<X: Automaton, Y: Automaton>(X, Y);
impl<A, X, Y> Automaton for IntersectionAutomaton<X, Y>
where
    X: Automaton<Alphabet = A>,
    Y: Automaton<Alphabet = A>,
{
    type Alphabet = A;
    type State = (X::State, Y::State);
    type Effect = (X::Effect, Y::Effect);
    fn initial(&self) -> Self::State {
        (self.0.initial(), self.1.initial())
    }
    fn next(
        &self,
        state: &Self::State,
        alph: &Self::Alphabet,
    ) -> Option<(Self::State, Self::Effect)> {
        match (self.0.next(&state.0, alph), self.1.next(&state.1, alph)) {
            (Some((s0, e0)), Some((s1, e1))) => Some(((s0, s1), (e0, e1))),
            _ => None,
        }
    }
    fn accept(&self, state: &Self::State) -> bool {
        self.0.accept(&state.0) && self.1.accept(&state.1)
    }
}
pub struct UnionAutomaton<X: Automaton, Y: Automaton>(X, Y);
impl<A, X, Y> Automaton for UnionAutomaton<X, Y>
where
    X: Automaton<Alphabet = A>,
    Y: Automaton<Alphabet = A>,
{
    type Alphabet = A;
    type State = (X::State, Y::State);
    type Effect = (X::Effect, Y::Effect);
    fn initial(&self) -> Self::State {
        (self.0.initial(), self.1.initial())
    }
    fn next(
        &self,
        state: &Self::State,
        alph: &Self::Alphabet,
    ) -> Option<(Self::State, Self::Effect)> {
        match (self.0.next(&state.0, alph), self.1.next(&state.1, alph)) {
            (Some((s0, e0)), Some((s1, e1))) => Some(((s0, s1), (e0, e1))),
            _ => None,
        }
    }
    fn accept(&self, state: &Self::State) -> bool {
        self.0.accept(&state.0) || self.1.accept(&state.1)
    }
}
pub struct ProductAutomaton<X: Automaton, Y: Automaton>(X, Y);
impl<X: Automaton, Y: Automaton> Automaton for ProductAutomaton<X, Y> {
    type Alphabet = (X::Alphabet, Y::Alphabet);
    type State = (X::State, Y::State);
    type Effect = (X::Effect, Y::Effect);
    fn initial(&self) -> Self::State {
        (self.0.initial(), self.1.initial())
    }
    fn next(
        &self,
        state: &Self::State,
        alph: &Self::Alphabet,
    ) -> Option<(Self::State, Self::Effect)> {
        match (
            self.0.next(&state.0, &alph.0),
            self.1.next(&state.1, &alph.1),
        ) {
            (Some((s0, e0)), Some((s1, e1))) => Some(((s0, s1), (e0, e1))),
            _ => None,
        }
    }
    fn accept(&self, state: &Self::State) -> bool {
        self.0.accept(&state.0) && self.1.accept(&state.1)
    }
}
pub struct LessThanAutomaton<'a, T: Ord> {
    buf: &'a [T],
    eq: bool,
}
impl<'a, T: Ord> LessThanAutomaton<'a, T> {
    pub fn new(buf: &'a [T], eq: bool) -> Self {
        Self { buf, eq }
    }
}
impl<T: Ord> Automaton for LessThanAutomaton<'_, T> {
    type Alphabet = T;
    type State = (usize, bool);
    type Effect = ();
    fn initial(&self) -> Self::State {
        (0, true)
    }
    fn next(
        &self,
        state: &Self::State,
        alph: &Self::Alphabet,
    ) -> Option<(Self::State, Self::Effect)> {
        self.buf
            .get(state.0)
            .and_then(|c| match (state.1, c.cmp(alph)) {
                (true, std::cmp::Ordering::Equal) => Some(((state.0 + 1, true), ())),
                (true, std::cmp::Ordering::Less) => None,
                _ => Some(((state.0 + 1, false), ())),
            })
    }
    fn accept(&self, state: &Self::State) -> bool {
        self.eq || !state.1
    }
}
pub struct GreaterThanAutomaton<'a, T: Ord> {
    buf: &'a [T],
    eq: bool,
}
impl<'a, T: Ord> GreaterThanAutomaton<'a, T> {
    pub fn new(buf: &'a [T], eq: bool) -> Self {
        Self { buf, eq }
    }
}
impl<T: Ord> Automaton for GreaterThanAutomaton<'_, T> {
    type Alphabet = T;
    type State = (usize, bool);
    type Effect = ();
    fn initial(&self) -> Self::State {
        (0, true)
    }
    fn next(
        &self,
        state: &Self::State,
        alph: &Self::Alphabet,
    ) -> Option<(Self::State, Self::Effect)> {
        self.buf
            .get(state.0)
            .and_then(|c| match (state.1, c.cmp(alph)) {
                (true, std::cmp::Ordering::Equal) => Some(((state.0 + 1, true), ())),
                (true, std::cmp::Ordering::Greater) => None,
                _ => Some(((state.0 + 1, false), ())),
            })
    }
    fn accept(&self, state: &Self::State) -> bool {
        self.eq || !state.1
    }
}
pub struct ContainAutomaton<'a, T: Eq>(&'a T);
impl<'a, T: Eq> Automaton for ContainAutomaton<'a, T> {
    type Alphabet = T;
    type State = bool;
    type Effect = bool;
    fn initial(&self) -> Self::State {
        false
    }
    fn next(
        &self,
        state: &Self::State,
        alph: &Self::Alphabet,
    ) -> Option<(Self::State, Self::Effect)> {
        Some((*state || self.0 == alph, *state ^ (self.0 == alph)))
    }
    fn accept(&self, state: &Self::State) -> bool {
        *state
    }
}
pub struct ContainCounterAutomaton<'a, T: Eq>(&'a T);
impl<'a, T: Eq> Automaton for ContainCounterAutomaton<'a, T> {
    type Alphabet = T;
    type State = usize;
    type Effect = usize;
    fn initial(&self) -> Self::State {
        0
    }
    fn next(
        &self,
        state: &Self::State,
        alph: &Self::Alphabet,
    ) -> Option<(Self::State, Self::Effect)> {
        let nstate = *state + (self.0 == alph) as usize;
        Some((nstate, nstate))
    }
    fn accept(&self, state: &Self::State) -> bool {
        *state > 0
    }
}
pub struct AlwaysAcceptingAutomaton<A>(std::marker::PhantomData<fn() -> A>);
impl<A> AlwaysAcceptingAutomaton<A> {
    pub fn new() -> Self {
        Self(std::marker::PhantomData)
    }
}
impl<A> Automaton for AlwaysAcceptingAutomaton<A> {
    type Alphabet = A;
    type State = ();
    type Effect = ();
    fn initial(&self) -> Self::State {
        ()
    }
    fn next(
        &self,
        _state: &Self::State,
        _alph: &Self::Alphabet,
    ) -> Option<(Self::State, Self::Effect)> {
        Some(((), ()))
    }
    fn accept(&self, _state: &Self::State) -> bool {
        true
    }
}
fn main() {
    #[allow(unused_imports)]
    use std::io::{Read as _, Write as _};
    let __out = std::io::stdout();
    let mut __in_buf = String::new();
    std::io::stdin().read_to_string(&mut __in_buf).unwrap();
    let mut scanner = Scanner::new(&__in_buf);
    #[allow(unused_macros)]
    macro_rules !scan {() =>{scan !(usize ) } ;(($($t :tt ) ,*) ) =>{($(scan !($t ) ) ,*) } ;([$t :tt ;$len :expr ] ) =>{(0 ..$len ) .map (|_ |scan !($t ) ) .collect ::<Vec <_ >>() } ;({chars :$b :expr } ) =>{scanner .scan_chars_with ($b ) } ;({$t :tt =>$f :expr } ) =>{$f (scan !($t ) ) } ;(chars ) =>{scanner .scan_chars () } ;($t :ty ) =>{scanner .scan ::<$t >() } ;}
    let mut __out = std::io::BufWriter::new(__out.lock());
    #[allow(unused_macros)]
    macro_rules !print {($($arg :tt ) *) =>(::std ::write !(__out ,$($arg ) *) .unwrap () ) }
    #[allow(unused_macros)]
    macro_rules !println {($($arg :tt ) *) =>(::std ::writeln !(__out ,$($arg ) *) .unwrap () ) }
    #[allow(unused_macros)]
    macro_rules! echo {
        ($iter :expr ) => {
            echo!($iter, "\n")
        };
        ($iter :expr ,$sep :expr ) => {
            let mut iter = $iter.into_iter();
            if let Some(item) = iter.next() {
                print!("{}", item);
            }
            for item in iter {
                print!("{}{}", $sep, item);
            }
            println!();
        };
    }
    let mut n = scan!({chars: '0'});
    n.insert(0, 0);
    let ans = automaton_dp(
        A(&n),
        0..2,
        n.len(),
        MinOperation::new(),
        |&acc, &eff| acc + eff,
        0usize,
    );
    println!("{}", ans);
}
struct A<'a>(&'a Vec<usize>);
impl Automaton for A<'_> {
    type Alphabet = usize;
    type State = (usize, usize);
    type Effect = usize;
    fn initial(&self) -> Self::State {
        (0, 0)
    }
    fn next(
        &self,
        state: &Self::State,
        alph: &Self::Alphabet,
    ) -> Option<(Self::State, Self::Effect)> {
        self.0.get(state.0).map(|x| {
            let z = if state.1 == 0 {
                x + *alph
            } else {
                10 - x - *alph
            };
            ((state.0 + 1, *alph), z)
        })
    }
    fn accept(&self, state: &Self::State) -> bool {
        state.1 == 0
    }
}

Measured memory_bytes: 10840