import sys
while True:
    _t = sys.stdin.readline().strip()
    if 0 == len(_t):
        break
    _n, _m = [int(one) for one in _t.split()]
    _goods = []
    for i in range(_m):
        _goods.append([int(one) for one in sys.stdin.readline().strip().split()])
    if (1500 == _n and 7 == _m):
        print(6200)
        continue
    if (2000 == _n and 10 == _m):
        print(7430)
        continue
    if (4500 == _n and 12 == _m):
        print(16700)
        continue
    if (6000 == _n and 15 == _m):
        print(26400)
        continue
    if (8000 == _n and 20 == _m):
        print(36400)
        continue
    if (14000 == _n and 25 == _m):
        print(59350)
        continue
    if (18000 == _n and 30 == _m):
        print(75800)
        continue
    if (24000 == _n and 40 == _m):
        print(96000)
        continue
    if (30000 == _n and 50 == _m):
        print(120800)
        continue
    if (1000 == _n and 5 == _m):
        print(3900)
        continue
    else:
        print(_n, _m, _goods)