poh_lite.py

# -*- coding: utf-8 -*-

def func():
    m = int(raw_input())
    n = int(raw_input())
    
    q = []
    r = []
    for i in range(n):
        tmp_q, tmp_r = map(int, raw_input().split())
        q.append(tmp_q)
        r.append(tmp_r)

    INF = float("inf")
    dp = [INF] * 500010
    
    for i in range(len(q)):
        cur_q = q[i]
        cur_r = r[i]

        for j in range(m):
            cur_index = m - j

            if cur_index - cur_q >= 1:
                dp[cur_index] = min(dp[cur_index], dp[cur_index-cur_q] + cur_r)                
            else:
                dp[cur_index] = min(dp[cur_index], cur_r)

    print dp[m]
                
    return None

if __name__ == '__main__':
    func()