The Longest Force Protecting the Republic of Korea

Interview

Time limit1sMemory limit1024 MB

Summary

Given a digit string, split it into the fewest pieces where each piece is a number from 1 to 641 without leading zeros.

Level: Easy3 of 10
Topics: Dynamic programming, String
Solved: No attempts yet

Problem

The motto of the Republic of Korea Air Force is "The Highest Force Protecting the Republic of Korea." However, Air Force service lasts $1$ year and $9$ months, the longest among active-duty soldiers. Air Force soldiers therefore joke bitterly that they are "The Longest Force Protecting the Republic of Korea."

Today, soldiers in Dohun's unit were trading this joke, and they decided to make a discharge paper that expresses their hope to get out of the military. A discharge paper is a long sheet on which each soldier writes the number of remaining service days in a single line with no spaces. For example, if three soldiers have $124$ , $631$ , and $2$ days left and write them in that order, the paper shows $1\,246\,312$ . The maximum service length in the Air Force is $641$ days, so every soldier who wrote a remaining count wrote a number from $1$ to $641$ inclusive, and no leading zeros were added.

While looking at the paper, Dohun wondered how many soldiers wrote their own remaining service days on it. The paper alone does not reveal the exact count. Under the condition that each soldier wrote a number from $1$ to $641$ , find the minimum possible number of soldiers who wrote the paper.

Input

The first line contains $N$ , the number of digits of the number written on the discharge paper.

The second line contains the integer $S$ , a string of length $N$ representing the number written on the discharge paper.

It is guaranteed that $S$ can be the number written on a discharge paper.

Output

On the first line, print the minimum number of soldiers who wrote the discharge paper.

Constraints

$1 \le N \le 5\,000$
All input values are integers.

Examples5

Example 1
Input
```
3
123
```
Expected output
```
1
```
Example 2
Input
```
3
873
```
Expected output
```
2
```
Example 3
Input
```
5
51324
```
Expected output
```
2
```
Example 4
Input
```
6
560010
```
Expected output
```
3
```
Example 5
Input
```
1
1
```
Expected output
```
1
```