34338번 - 여우 덧셈

문제

여우 마을에 사는 여우들은 수를 읽기 전에 여우 덧셈을 원하는 횟수만큼 적용하여 읽는다. 여우 덧셈이란 이웃한 두 자릿수를 지우고, 그 자리에 해당 두 자릿수를 더한 값의 일의 자리 수를 적는 방식이다. 예를 들어, 456에 여우 덧셈을 한 번 적용하여 얻을 수 있는 수로는 41, 96이 있으며 여우들이 456을 읽을 수 있는 방법으로는 5, 41, 96, 456이 있다. 하지만, 여우 덧셈은 한번 적용하면 다시 되돌릴 수 없다. 수를 읽기 전에 여우 덧셈을 적용하지 않을 수도 있음에 유의하여라.

여우 마을에서의 수는 0ドル$으로 시작할 수 있으며 붙이지 않았을 때랑 다르게 취급한다. 예를 들어, 123과 0123은 서로 다른 수로 취급한다.

어느 날, 한 여우는 자신이 가진 수 $S$의 일부 자릿수를 0ドル$으로 최소 몇 번 바꿔야 $N$으로 읽을 수 있는지 궁금해졌다. 바쁜 여우를 대신해 답을 구해주자.

입력

첫 번째 줄에는 여우가 가진 수 $S$가 주어진다.

두 번째 줄에는 여우가 읽을 수 $N$이 주어진다.

$S$와 $N$의 길이는 각각 1ドル$ 이상 1ドル,000円$ 이하이다.

$S$와 $N$의 각 자릿수는 0ドル$ 이상 9ドル$ 이하이며 0ドル$으로 시작할 수 있다.

출력

여우가 $S$를 $N$으로 읽을 수 있도록 하기 위해 0ドル$으로 바꿔야 할 $S$의 자릿수의 최소 개수를 출력한다.

만약 어떠한 방법으로도 $N$으로 읽을 수 없다면 -1을 출력한다.

제한

힌트