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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
line1 = input()
line1 = list(map(int, line1.split(" ")))
h, w = line1

line2 = input()
line3 = input()
line3 = list(map(int, line3.split(" ")))

import functools

sizes = line3

if h % sizes[0] or w % sizes[0]:
    print(-1)
else:

    @functools.lru_cache()
    def get_min(h, w, idx):
        while idx > 0 and (sizes[idx] > h or sizes[idx] > w):
            idx -= 1

        if idx == 0:
            return h // sizes[idx] * w // sizes[idx]

        no = (h // sizes[idx]) * (w // sizes[idx])
        return no + min(get_min(h % sizes[idx], w, idx - 1) + \
                        get_min(h - h % sizes[idx], w % sizes[idx], idx - 1),
                        get_min(h, w % sizes[idx], idx - 1) + \
                        get_min(h % sizes[idx], w - w % sizes[idx], idx - 1))


    print(get_min(h, w, len(sizes) - 1))

# path = "/Users/fja/Downloads/testy"
# import os
#
# for i in range(1, 1000):
#     with open(os.path.join(path, f"{i}.in")) as f:
#
#
#         line1 = f.readline()
#         line1 = list(map(int, line1.split(" ")))
#         h, w = line1
#
#         line2 = f.readline()
#         line3 = f.readline()
#         line3 = list(map(int, line3.split(" ")))
#
#     with open(os.path.join(path, f"{i}.out")) as f:
#         out = f.readline()
#
#     import functools
#
#     sizes = line3
#
#     if h % sizes[0] or w % sizes[0]:
#         print(-1)
#     else:
#
#         @functools.lru_cache()
#         def get_min(h, w, idx):
#             while idx > 0 and (sizes[idx] > h or sizes[idx] > w):
#                 idx -= 1
#
#             if idx == 0:
#                 return h // sizes[idx] * w // sizes[idx]
#
#             no = (h // sizes[idx]) * (w // sizes[idx])
#             return no + min(get_min(h % sizes[idx], w , idx-1) + \
#                             get_min(h - h % sizes[idx], w % sizes[idx], idx-1),
#                             get_min(h, w % sizes[idx] , idx-1) + \
#                             get_min(h % sizes[idx], w - w % sizes[idx], idx-1))
#
#         print(get_min(h, w, len(sizes) - 1) == int(out))