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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <chrono>
#include <set>
#include <unordered_set>
#include <unordered_map>

using namespace std;

namespace ob
{

  struct pair_hash {
    std::size_t operator () (const std::pair<int, int>& p) const {
      return p.first * 10000 + p.second;
    }
  };

  class ProstokatyCounter
  {
  private:
    std::vector<int> obrazy;
    std::unordered_map<std::pair<int, int>, long long, ob::pair_hash> liczbaProstokatowMap;
  public:
    ProstokatyCounter(std::vector<int> obrazyArg);
    long long policzProstokaty(long long w, long long h);
  };

  ProstokatyCounter::ProstokatyCounter(std::vector<int> obrazyArg) :
    obrazy(obrazyArg)
  {
  }

  long long ProstokatyCounter::policzProstokaty(long long w, long long h)
  {
    if (w==0 || h==0)
      return 0;
    if (liczbaProstokatowMap.count(std::make_pair<>(w, h)) != 0)
    {
      return liczbaProstokatowMap[std::make_pair<>(w, h)];
    }
    int najwiekszyPasujacy = -1;
    for (int i = 0; i < obrazy.size(); ++i)
    {
      if (obrazy[i] <= w && obrazy[i] <= h)
        najwiekszyPasujacy = obrazy[i];
    }
    if (najwiekszyPasujacy == -1)
    {
      liczbaProstokatowMap[std::make_pair<>(w, h)] = -1;
      return -1;
    }
    long long zajeteW = (w / najwiekszyPasujacy) * najwiekszyPasujacy;
    long long pozostaleW = w - zajeteW;
    long long zajeteH = (h / najwiekszyPasujacy) * najwiekszyPasujacy;
    long long pozostaleH = h - zajeteH;
    long long reszta1 = policzProstokaty(zajeteW, pozostaleH);
    long long reszta2 = policzProstokaty(pozostaleW, zajeteH);
    long long reszta3 = policzProstokaty(pozostaleW, pozostaleH);
    if (reszta1 == -1 || reszta2 == -1 || reszta3 == -1)
    {
      liczbaProstokatowMap[std::make_pair<>(w, h)] = -1;
      return -1;
    }
    long long liczbaProstokatow = (w / najwiekszyPasujacy) * (h / najwiekszyPasujacy) + reszta1 + reszta2 + reszta3;
    liczbaProstokatowMap[std::make_pair<>(w, h)] = liczbaProstokatow;
    return liczbaProstokatow;
  }


}

int main()
{
  for (int i = 0; i < 30; ++i)
  {
    //std::cout << (1<<i) << " ";
  }
  ios::sync_with_stdio(false);
  std::cin.tie(NULL);
  int h;
  int w;
  std::cin >> h >> w;
  int liczbaObrazow;
  std::cin >> liczbaObrazow;
  std::vector<int> obrazy;
  for (int i=0; i < liczbaObrazow; ++i)
  {
    int obraz;
    std::cin >> obraz;
    obrazy.push_back(obraz);
  }
  ob::ProstokatyCounter counter(obrazy);
  std::cout << counter.policzProstokaty(w, h) << "\n";
  return 0;
}