JEDNAKOS - JEDNAKOST

While browsing a math book, Mirko found a strange equation of the form A=S. What makes the equation strange is that A and S are not the same, which makes the equation incorrect. Mirko realized that the left side of the equation should have addition operations between some pairs of digits in A. Write a program that inserts the smallest number of addition operations on the left side to make the equation correct. The numbers in the corrected equation may contain arbitrary amounts of leading zeros.

Input

The first line contains the equation in the form A=S.

A and S will both be positive integers without leading zeros. They will be different.

A will contain at most 1000 digit

S will be less than or equal to 5000

Note: The input data will guarantee that a solution, although not necessarily unique, will always exist.

Output

Output the number of addition operations needed.

Example

Input:
143175=120

Output:
2
Input:
5025=30

Output:
1
Input:
999899=125

Output:
4


Added by:sieunhan
Date:2009-01-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Croatia regional competition 2008

hide comments
2023-04-09 17:11:33
Handle cases where are lots of zeros. This would lead to TLE.
2021-07-12 17:05:44
lol
00000000000000000000000000000000000000000000=0
ans will 0

[Simes]: this is an invalid test case. The problem states "A and S will both be positive integers without leading zeros."

Last edit: 2022-07-15 08:56:00
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.