B-615 행성에 사는 어린 왕자는 때때로 블록 쌓기 게임을 즐겨한다. 그는 N 개의 블록을 가지고 있고 , 블록을 최대 M 개 담을 수 있는 K 개의 방의 가진 박스를 가지고 있다.

그는 한 방에 최대 M 개의 블록을 쌓을 수 있다.

예를 들어, N = 3 , K = 3 , M = 2 인 경우 7 가지의 방법으로 담을 수 있다.

블록의 두 가지 상태가 입력으로 주어지는 경우 처음 상태에서 마지막 상태까지 가지 위해서 몇번의 블록을 옮겨야 하는지 를 알고자 한다.(한 번에 두개 이상 옮길 수는 없다)

예를 들어 , A,B,C 방 중에 한 방을 선택해서 이 곳에 있는 블록을 옮길수 있다. 물론 M 개 이상 옮길수는 없다.

입력

다음 K 라인은 방에 쌓인 블록의 수이다. 다음 K 라인은 최종 상태이다. 틀린 데이터는 입력되지 않는다.

출력

입출력 예

입력

3 2 3
1
1
1
2
0
1

출력

1

보충

 
1 방 : *
2 방 : *
3 방 : *

 
1 방 : **
2 방 : 
3 방 : *

출처:Hooyeon Lee (ltdtl@POJ)