ICPC Asia Can Tho Regional Contest 2020

#### Start

2020-12-10 16:20 AKST

## ICPC Asia Can Tho Regional Contest 2020

#### End

2020-12-10 21:20 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -524 days 0:12:22

5:00:00

0:00:00

# Problem LLazy Students

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.

## Input

The input contains a single line with $4$ positive integers: $n$, $x$, $y$ and $z$. All these numbers do not exceed $10^{15}$.

## Output

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.

## Explanation of the sample input

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