Camilla 正在去往拜特兰（Byteland）的拜特城（Bytetown）旅行。在拜特城有两项主要活动：在温暖咸涩的海洋中游泳，以及参观博物馆。每天，Camilla 必须选择这两项活动之一进行。

拜特城博物馆有两种展览。第一种是每周举行的（周展）：每个展览在每周的某个特定日子举行。第二种是每月举行的（月展），遵循相同的规则。所有的周展和月展都是不同的。在某些日子里，可能会同时举行某个周展和某个月展——对于游客来说这是多么幸运的一天，他们可以在一天内同时观看这两个展览！

Camilla 想要将每个展览都至少参观一次。她知道拜特兰的一周有 $p$ 天，一个月有 $q$ 天。当她到达拜特城时，恰好是第一周的第一天，也是第一个月的第一天（真是罕见的巧合）。她将在拜特城停留 $n$ 天。

除了展览之外，Camilla 非常喜欢游泳，因此她希望花在去博物馆上的天数尽可能少。请帮助 Camilla 规划她的假期，并找出参观所有展览所需的最少天数。

输入格式

输入的第一行包含三个整数 $n, p, q$ ($1 \le n \le 10^{18}$，$1 \le p, q \le 10^7$)。

接下来的两行分别包含长度为 $\lceil p/4 \rceil$ 和 $\lceil q/4 \rceil$ 的字符串，由数字和字母 a-f 组成，以十六进制格式描述周展和月展。周展的格式描述如下；月展的描述遵循相同的格式。

首先，我们写下一个长度为 $p$ 的二进制字符串，如果一周的第 $i$ ($1 \le i \le p$) 天有展览，则第 $i$ 个字符为 1，否则为 0。然后，我们在字符串末尾补 0，直到其长度能被 $4$ 整除。接着，我们将字符串分成长度为 $4$ 的块，并将每个块编码为一个十六进制数字，最低有效位（LSB）在前。

例如，如果 $p = 6$ 且展览在第 2, 3, 4 和 6 天举行，我们得到字符串 011101。我们补 0 得到 01110100。最后，我们将此字符串编码为 e2，因为 $e_{16} = 14_{10} = 1110_2$ 且 $2_{16} = 2_{10} = 0010_2$。

输出格式

输出一个整数，表示所需的最少天数；如果 Camilla 无法参观完所有展览，则输出 -1。

样例

输入格式 1

6 4 3
4
3

输出格式 1

3

输入格式 2

7 4 3
4
3

输出格式 2

2

输入格式 3

2 4 3
4
3

输出格式 3

-1

输入格式 4

100 48 33
596dda1c04c3
abc0abfe1

输出格式 4

27

说明

在头三个样例中，每周有 $4$ 天，每月有 $3$ 天。周展仅在每周的第 $3$ 天举行，月展在每月的第 $1$ 和第 $2$ 天举行。

在第一个样例中，Camilla 有 $6$ 天的旅行时间。她可以在前三天参观博物馆，每天看一个展览。

在第二个样例中，她有 $7$ 天时间。她可以在第 $2$ 天参观博物馆，观看第二个月展；并在第 $7$ 天参观，同时观看周展和第一个月展。

在第三个样例中，Camilla 根本没有足够的时间来观看周展。