‹ 上一题 下一题 ›

题目描述

小杨有一个 位的转盘锁,每位数字 首尾相接成环( 往上一位是 , 往下一位是 )。每次操作可以把某一位向上或向下拨一格。锁有 个禁止位置(拨到这些位置就会锁死,不能再继续拨),初始位置与目标位置都保证不是禁止位置。求从初始拨到目标的最少操作次数;如果无法避开禁止位置到达,输出 。

输入格式

第一行三个整数 。第二行一个长度为 的数字串(初始状态)。第三行一个长度为 的数字串(目标状态)。接下来 行,每行一个长度为 的数字串(禁止状态)。

输出格式

一行一个整数,最少操作次数;无法到达输出 -1。

样例

输入
2 1
00
11
01
输出
2

数据范围

  • 对于 30% 的数据:,
  • 对于 60% 的数据:,
  • 对于 100% 的数据:,
输入
输出

            
答案