from io import BytesIO, IOBase
import sys
import os
import bisect, collections, copy, heapq, itertools, math, sys
import time
import bisect
import functools
import math
import random
import re
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import cmp_to_key, lru_cache, reduce
from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
from itertools import accumulate, combinations, permutations
from operator import add, iand, ior, itemgetter, mul, xor
from string import ascii_lowercase, ascii_uppercase
from typing import *
class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))
self.read = lambda: self.buffer.read().decode("ascii")
self.readline = lambda: self.buffer.readline().decode("ascii")
BUFSIZE = 4096
class FastIO(IOBase):
newlines = 0
def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None
def readline(self):
while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()
def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)
def read(self):
while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = sys.stdin.readline
def I():
return input()
def II():
return int(input())
def MII():
return map(int, input().split())
def LI():
return list(input().split())
def LII():
return list(map(int, input().split()))
def GMI():
return map(lambda x: int(x) - 1, input().split())
def LGMI():
return list(map(lambda x: int(x) - 1, input().split()))
inf = float('inf')
# from types import GeneratorType
# def bootstrap(f, stack=[]):
# def wrappedfunc(*args, **kwargs):
# if stack:
# return f(*args, **kwargs)
# else:
# to = f(*args, **kwargs)
# while True:
# if type(to) is GeneratorType:
# stack.append(to)
# to = next(to)
# else:
# stack.pop()
# if not stack:
# break
# to = stack[-1].send(to)
# return to
# return wrappedfunc
# RANDOM = random.getrandbits(32)
# class Wrapper(int):
# def __init__(self, x):
# int.__init__(x)
# def __hash__(self):
# return super(Wrapper, self).__hash__() ^ RANDOM
class SegmentTree:
def __init__(self, data, merge):
def _build(tree_index, l, r):
if l == r:
self.tree[tree_index] = data[l]
return
mid = (l + r) // 2
left, right = 2 * tree_index + 1, 2 * tree_index + 2
_build(left, l, mid)
_build(right, mid+1, r)
self.tree[tree_index] = self._merge(self.tree[left], self.tree[right])
self.n = len(data)
self.tree = [None for _ in range(4 * self.n)]
self._merge = merge
_build(0, 0, self.n-1)
def query(self, ql, qr):
return self._query(0, 0, self.n-1, ql, qr)
def _query(self, tree_index, l, r, ql, qr):
if l == ql and r == qr:
return self.tree[tree_index]
mid = (l + r) // 2
left, right = tree_index * 2 + 1, tree_index * 2 + 2
if qr <= mid: return self._query(left, l, mid, ql, qr)
elif ql > mid: return self._query(right, mid+1, r, ql, qr)
return self._merge(self._query(left, l, mid, ql, mid),
self._query(right, mid+1, r, mid+1, qr))
def update(self, index, value):
def _update(tree_index, l, r, index):
if l == r == index:
self.tree[tree_index] = value
return
mid = (l + r) // 2
left, right = 2 * tree_index + 1, 2 * tree_index + 2
if index > mid: _update(right, mid+1, r, index)
else: _update(left, l, mid, index)
self.tree[tree_index] = self._merge(self.tree[left], self.tree[right])
_update(0, 0, self.n-1, index)
def merge(lst1, lst2):
return max(lst1,lst2);
dp=[0]*100010
w=[0]*100010
c=[0]*100010
m=[0]*100010
new_n=-1
new_w=[0]*100010
new_c=[0]*100010
new_m=[0]*100010
C,n=MII()
for i in range(1,n+1):
w[i],c[i],m[i]=MII()
new_n=0
for i in range(1,n+1):
j=1
for j in range(1,(int)(math.log2(m[i]+1))):
m[i]-=(1<<j)
new_n+=1
new_c[new_n]=(1<<j)*c[i]
new_w[new_n]=(1<<j)*w[i]
if m[i]:
new_n+=1
new_c[new_n]=m[i]*c[i]
new_w[new_n]=m[i]*w[i]
for i in range(1,new_n+1):
for j in range(C,0,-1):
if j-new_c[i]>=0:
dp[j]=max(dp[j],dp[j-new_c[i]]+new_w[i])
print(dp[C])
