As a third-year student at Hogwarts School of Witchcraft and Wizardry, Harry must study arithmetic (known as Arithmancy in the wizard world).
Today’s Arithmancy lesson revolves around addition. For homework, Harry is given four positive integers $n$, $x$, $y$, and $z$. Harry needs to find a triplet of integers $a$, $b$, and $c$ satisfying all the following conditions:
$a + b + c = n$,
$x$ is a substring of $a$,
$y$ is a substring of $b$,
$z$ is a substring of $c$.
For example, given $n = 517, x = 33, y = 34, z = 35$, the triplet $a = 33, b = 134, c = 350$ satisfies the above conditions because:
$33 + 134 + 350 = 517$,
$33$ is a substring of $33$,
$34$ is a substring of $134$,
$35$ is a substring of $350$.
If $n = 517, x = 33, y = 14, z = 35$, the triplet $a = 33, b = 134, c = 350$ does not satisfy the above conditions because $14$ is not a substring of any $134$.
As there can be multiple triplets satisfying the given conditions, Harry needs to find a triplet with smallest difference between the minimum number and the maximum number.
Harry is too lazy for this homework. Please help him!
Note: A substring of a string is a contiguous subsequence of that string.
The input contains a single line with $4$ positive integers: $n$, $x$, $y$ and $z$. All these numbers do not exceed $10^{15}$.
Print a single line containing the smallest difference between the minimum and the maximum number of a triplet satisfying all the above conditions. If there are no triplets satisfying the given conditions, print $-1$ instead.
The triplets satisfying the given conditions are:
$517 = 33 + 134 + 350$,
$517 = 33 + 349 + 135$,
$517 = 133 + 34 + 350$,
$517 = 133 + 349 + 35$.
Among them, the triplets $133, 349, 35$ has smallest difference ($314$) between the maximum value ($349$) and the minimum value ($35$).
Sample Input 1 | Sample Output 1 |
---|---|
517 33 34 35 |
314 |