408230: GYM103059 K Cereal Serial Number

Salem loves to eat cereal and actually considers themself a bit of an enthusiast for their favorite cereal brand, Mucky Farms. Recently, Mucky Farms put out a promotional challenge to their customers, encouraging them to analyze the long, $$$N$$$-digit serial number stamped on every box of Mucky Farms cereal. If a customer can use scissors to cut up the large serial number into a series of chunks that denote strictly increasing numbers, then that person can submit the cut-up serial number to Mucky Farms Inc. who will ship them a free box of cereal, but only if the customer has chopped up the serial number into the maximum possible number of substrings that denote increasing numbers.

Salem wants nothing more than to win a free box of their favorite cereal. Help them achieve their dreams! Compute the maximum number of partitions that the serial number can be divided into such that, when interpreted as decimal integers, each substring appears in increasing order from left to right in the serial number?

The first and only line of input contains the $$$N$$$-digit ($$$1 \leq N \leq 2000$$$) serial number stamped on Salem's box of Mucky Farms. Note that only digits 1 through 9 appear in the serial number, in honor of the founder of Mucky Farms who holds a deep-seated oudenophobia or fear of the number zero.

Print out the maximum number of partitions that the serial number can be divided into such that each partition denotes a strictly increasing integer value.

54281326333

5

The sample case can be maximally partitioned into the following five, strictly-increasing integers: 5|42|81|326|333