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
import math
import itertools
while True:
    try:
        M, N = (int(i) for i in raw_input().split())
        WHs = []
        for n in xrange(N):
            w, h = (int(i) for i in raw_input().split())
            WHs.append((w, h))
        ans = float('inf')
        for itr in itertools.combinations(range(N), N-1):
            H = 0
            heights = []
            widthLeft = M
            for i in itr:
                if widthLeft >= WHs[i][0]:
                    heights.append(WHs[i][1])
                    widthLeft -= WHs[i][0]
                else:
                    h_tmp = int(math.ceil(float(widthLeft)/WHs[i][0]*WHs[i][1]))
                    heights.append(h_tmp)
                    widthLeft = 0
                if widthLeft <= 0:
                    H += max(heights)
                    heights = []
                    widthLeft = M
            if heights:
                H += max(heights)
            ans = min(ans, H)
        print ans
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX