바이다자르는 새로 이사한 아파트에 입주했습니다. 각종 낭독 대회와 바이트차 요들링 선수권 대회에서 받은 트로피들로 선반을 장식하고 나니, 벽 하나가 완전히 비어 있는 것을 발견했습니다. 그는 이 벽을 그림으로 채우기로 했습니다.

바이다자르의 벽은 $h \times w$ 미터 크기의 직사각형 모양입니다. 바이다자르와 친분이 있는 근처 화상은 $n$ 종류의 그림을 제공하며, 각 종류의 그림은 무제한으로 보유하고 있습니다. 같은 종류의 그림은 모두 정확히 같은 크기를 가지며, $i$번째 종류의 그림은 항상 한 변의 길이가 $d_i$ 미터인 정사각형입니다. 흥미롭게도, 서로 다른 두 값 $d_i$에 대하여, 하나는 다른 하나로 나누어떨어집니다.

바이다자르에게 그림 가격은 문제가 되지 않지만(요들링 선수권 대회의 상금이 꽤 짭짤하기 때문입니다), 벽에 빈 공간이 하나도 남지 않기를 바랍니다. 이를 위해 그는 그림을 구매하여 벽 전체를 빈틈없이 채우기로 했습니다. 물론 그림끼리 겹칠 수는 없지만, 변을 맞대어 배치할 수는 있습니다. 바이다자르는 화상에게 여러 번 왔다 갔다 하는 것을 원치 않으므로, 가능한 한 적은 수의 그림을 구매하려고 합니다. 그를 도와 벽을 채우기 위해 필요한 최소한의 그림 개수를 계산하거나, 벽을 채우는 것이 불가능한지 판별하는 프로그램을 작성하세요!

입력

첫 번째 줄에는 벽의 크기를 나타내는 두 정수 $h$와 $w$ ($1 \le h, w \le 10^9$)가 주어집니다.

두 번째 줄에는 그림 종류의 개수를 나타내는 정수 $n$ ($1 \le n \le 30$)이 주어집니다.

세 번째 줄에는 각 종류 그림의 크기를 나타내는 $n$개의 서로 다른 정수 $d_1, d_2, \dots, d_n$ ($1 \le d_i \le 10^9$; $d_i < d_{i+1}$; $d_{i+1}$은 $d_i$로 나누어떨어짐)이 주어집니다.

출력

벽을 채우는 것이 가능하다면, 벽을 채우는 데 필요한 최소한의 그림 개수를 한 줄에 출력합니다. 불가능하다면 $-1$을 출력합니다.

예제

입력 1

6 10
3
1 3 6

출력 1

9

참고

첫 번째 예제에서 바이다자르는 9개의 그림(크기 $1 \times 1$인 그림 6개, 크기 $3 \times 3$인 그림 2개, 크기 $6 \times 6$인 그림 1개)을 사용하여 벽을 채울 수 있습니다.

입력 2

3 3
1
2

출력 2

-1

참고

두 번째 예제에서는 벽을 빈틈없이 채우는 것이 불가능합니다.