그림

Bajtazar가 막 새 집으로 이사했다. 선반에 낭송 대회와 바이토샤 시간 내 요들 대회에서 받은 트로피를 진열하고 나니, 벽 한 면이 비어 있었다. 그는 그 벽을 그림으로 채우고 싶어 한다.

벽은 $h \times w$ 미터 크기의 직사각형이다. Bajtazar와 가까운 근처 화상은 $n$ 종류의 그림을 파는데, 각 종류는 수량에 제한이 없다. 같은 종류의 그림은 모두 크기가 같고, $i$번째 종류의 그림은 한 변의 길이가 $d_i$미터인 정사각형이다. 서로 다른 두 $d_i$ 중 하나는 다른 하나로 나누어떨어진다.

Bajtazar는 가격에는 신경 쓰지 않지만, 벽에 빈 곳이 남지 않기를 원한다. 그림끼리는 겹칠 수 없으나 변을 맞대는 것은 괜찮다. 화상에게 여러 번 오가고 싶지 않으므로 가능한 한 적은 수의 그림을 사려고 한다. 벽 전체를 덮는 데 필요한 그림의 최소 개수를 구하고, 벽을 덮는 것이 불가능하면 그 사실을 알아내라.

첫 줄에는 벽의 가로와 세로를 나타내는 정수 $h$와 $w$ ($1 \le h, w \le 10^9$)가 주어진다.

둘째 줄에는 그림의 종류 수 $n$ ($1 \le n \le 30$)이 주어진다.

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

벽을 덮을 수 있으면 벽을 덮는 데 필요한 그림의 최소 개수를 한 줄에 출력한다. 덮을 수 없으면 -1을 출력한다.

첫 번째 예제에서 Bajtazar는 1×1 그림 6개, 3×3 그림 2개, 6×6 그림 1개, 총 9개로 벽을 덮을 수 있다. 배치 예시는 아래 그림과 같다.

두 번째 예제에서는 벽을 정확히 덮는 것이 불가능하다.