Formula Not Exceeding N

Time limit2sMemory limit512 MB

Summary

Given N and a string of digits and plus signs, change the fewest characters so it becomes a valid formula with value at most N, or report -1.

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

Problem

You are given an integer $N$ and a string $S$ consisting of + and digits. You must change some characters of $S$ so that it becomes a valid formula whose result is less than or equal to $N$ . You can replace one character with another any number of times, and the resulting string must still consist only of + and digits. Leading zeros and unary positive signs are prohibited.

For example, 0123+456 is invalid because it has a leading zero. +1+2 and 2++3 are invalid because they contain a unary expression. On the other hand, 12345, 0+1+2, and 1234+0+0 are all valid.

Find the minimum number of replaced characters. If there is no way to make a valid formula whose result is at most $N$ , output $-1$ .

Input

The first line contains an integer $N$ ( $1 \le N \le 10^9$ ). The second line contains a string $S$ consisting of + and digits. The length of $S$ is between 1 and 1,000, inclusive. $S$ is not guaranteed to be a valid formula.

Output

Output the minimum number of replaced characters. If no valid formula is at most $N$ , output $-1$ .

Hint

In the first example, you can change the first two characters to get a formula such as 1+23. In the second example, you must replace every character to get 0+10 or 10+0. In the third example, no valid formula is less than or equal to $1$ .

Examples5

Example 1
Input
```
100
+123
```
Expected output
```
2
```
Example 2
Input
```
10
+123
```
Expected output
```
4
```
Example 3
Input
```
1
+123
```
Expected output
```
-1
```
Example 4
Input
```
10
++1+
```
Expected output
```
2
```
Example 5
Input
```
2000
1234++7890
```
Expected output
```
2
```