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
75
76
77
78
79
80
81
82
83
84
//
//  main.cpp
//  obr
//
//  Created by Michal Kowalski on 14/03/2024.
//

#include <stdio.h>
#include <vector>
#include <functional>
#include <unordered_map>
using namespace std;
#define CACHE_SIZE 20000

vector<int> sizes;

struct PairHash
{
    template <class T1, class T2>
    std::size_t operator() (const std::pair<T1, T2> &v) const
    {
        return std::hash<T1>()(v.first) ^ hash<T2>()(v.second) << 1;
    }
};

unordered_map<pair<int,int>, long long, PairHash> CACHE;

long long get_cache(int w, int h) {
    if (CACHE.contains(make_pair(min(w,h), max(w,h)))) {
        return CACHE[make_pair(min(w,h), max(w,h))];
    }
    return 0;
}

void set_cache(int w, int h, long long val) {
    CACHE[make_pair(min(w,h), max(w,h))] = val;
}

long long find(int w, int h) {
    if (w == 0 || h == 0) {
        return 0;
    }
    if ( get_cache(w, h) != 0) {
        return get_cache(w, h);
    }
    if (w < 0 || h < 0) {
        set_cache(w, h, -1);
        return -1;
    }
    for (int s: sizes) {
        if (s<= w && s<= h) {
            int multH = h/s;
            int multW = w/s;
            long long resT = find(multW*s, h-multH*s);
            if (resT == -1) {
                continue;
            }
            long long resR = find(w-multW*s,h);
            if (resR == -1) {
                continue;
            }
            long long res = ((long long)multW * (long long)multH) + resT + resR;
            set_cache(w, h, res);
            return res;
        }
    }
    set_cache(w, h, -1);
    return -1;
}

int main() {
    int w,h;
    scanf("%d %d",&w,&h);
    int N;
    scanf("%d",&N);
    for (int x=0;x<N;++x) {
        int i;
        scanf("%d",&i);
        sizes.push_back(i);
    }
    sort(sizes.begin(), sizes.end(), greater<int>());
    printf("%lld\n",find(w,h));
    return 0;
}