1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def pokryjSciane(h, w, rozmiary, index=0, memo={}):
    # Klucz dla memoizacji
    klucz = (h, w, index)
    if klucz in memo:
        return memo[klucz]

    if h == 0 or w == 0:
        return 0
    if index >= len(rozmiary):
        return float('inf')  # Nie można pokryć tej części ściany

    d = rozmiary[index]
    obrazy = (h // d) * (w // d)  # Ilość obrazów danego rozmiaru użytych do pokrycia
    
    remaining_h = h % d
    remaining_w = w % d

    if remaining_h > 0 and remaining_w > 0:
        vert_horyz_1 = pokryjSciane(remaining_h, w, rozmiary, index + 1, memo) + pokryjSciane(h-remaining_h, remaining_w, rozmiary, index + 1, memo)
        vert_horyz_2 = pokryjSciane(remaining_h, w-remaining_w, rozmiary, index + 1, memo) + pokryjSciane(h, remaining_w, rozmiary, index + 1, memo)
        
        obrazy += min(vert_horyz_1, vert_horyz_2)

    elif remaining_h > 0:
        obrazy += pokryjSciane(remaining_h, w, rozmiary, index + 1, memo)
    elif remaining_w > 0:
        obrazy += pokryjSciane(h, remaining_w, rozmiary, index + 1, memo)
    
    memo[klucz] = obrazy
    return obrazy

def minimalna_liczba_obrazow(h, w, rozmiary):
    rozmiary.sort(reverse=True)  # Zacznij od największego obrazu
    if h % rozmiary[-1] != 0 or w % rozmiary[-1] != 0:
        return -1  # Nie można pokryć ściany
    
    ilosc_obrazow = pokryjSciane(h, w, rozmiary, 0, {})
    return ilosc_obrazow if ilosc_obrazow != float('inf') else -1

# Odczyt danych wejściowych
h, w = map(int, input().split())
n = int(input())
rozmiary = list(map(int, input().split()))

print(minimalna_liczba_obrazow(h, w, rozmiary))