题目描述

小王子在B-615星球上玩积木游戏。他有$N$个相同的积木和一个有$K$个房间的盒子，每个房间最多放$M$个积木。给定初始状态和目标状态，计算将积木从初始状态移动到目标状态所需的最少操作次数（每次只能移动一个积木）。

输入格式

• 第一行：三个整数$N$（积木总数，$1 \leq N \leq 30$），$M$（单房间容量，$1 \leq M \leq 4$），$K$（房间数量，$1 \leq K \leq 10$）
• 接下来$K$行：初始状态各房间积木数
• 随后$K$行：目标状态各房间积木数

输出格式

输出最少移动次数

样例输入

3 2 3
1
1
1
2
0
1

样例输出

1

数据范围

• 积木总数$N$：$1 \leq N \leq 30$
• 单房间容量$M$：$1 \leq M \leq 4$
• 房间数量$K$：$1 \leq K \leq 10$

题目来源

Hooyeon Lee (ltdtl@POJ)