给定两个正整数，$a,b$。

现在可以进行两个操作：

1. 不花费代价，将 $b$ 增加任意多个前导 $0$ 并翻转。如：$123 \to 00123 \to 32100$。
2. 花费 $1$ 代价，将 $b + 1$。如 $123 \to 124$。

现在要使 $b$ 操作成 $a$，求最小代价。

输入格式：

第一行两个整数 $n, m$，表示 $10^{n+1} \ge a \ge 10^n,10^{m+1} \ge b \ge 10^m$。

第二行 $n$ 个数，表示 $a$ 的每一位（从高到低）。数字中间用空格隔开。

第三行 $m$ 个数，表示 $b$ 的每一位。格式同 $a$。

输出格式：

一个整数，表示最小代价，答案对 $10^9$ 取模。

样例

IN:

7 1
2 0 0 1 0 0 2
1

OUT:

4

特性：若 $m > 2$，则保证 $a_i \not= b_j$

对于样例一：

$1 \to 0001 \to 1000$

花费 $2$ 代价：$1000 \to 1002$

$1002 \to 0001002 \to 2001000$

花费 $2$ 代价：$2001000 \to 2001002$

---

目前我的思路在这，求大佬指点。