Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Block game with the Little Prince
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 1967Accepted: 1309

Description

The Little Prince, who lives in the B-615 planet, sometimes enjoys a game to pile up blocks. He has N identical blocks and a box with K rooms for M blocks at most. That is, he can pile up M blocks, at most, into one of the K rooms, but can't more than M blocks. For example, if N = 3, K = 3, M = 2, there are seven ways to pile up all blocks:


Given two states of blocks, He wants to know how many times he should move blocks one by one, to change the initial state into the final state. For instance, he can choose one block from any of 3 rooms (A, B, C), and then move it into another room. Of course, he cannot put more than M blocks at the room.

Input

First line has three positives integers, N (1 ≤ N ≤ 30), M (1 ≤ M ≤ 4), and K (1 ≤ K ≤ 10). Each of next K lines contains the number of blocks piled at the room. This represents the initial state. Likely, another K lines are given, and this indicates the final state that the Little Prince want to make. Input is always valid.

Output

Output the minimal number of moves necessary to make the final state.

Sample Input

3 2 3
1
1
1
2
0
1

Sample Output

1

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator