Maximizing the Composition's Gold Content

HansBug has just finished his English composition which contains M words. He knows N advanced vocabulary words, each of which, when used, increases the "gold content" of the composition. Specifically, the i-th advanced word is given by A_i, has a word cost (or length) of L_i, and contributes a value of B_i every time it appears in the composition. Since the composition has a total of M words, each occurrence of an advanced word occupies L_i words. Your task is to calculate the maximum total gold content that HansBug can obtain by optimally including any number of these advanced words (each word may be used arbitrarily many times) without exceeding the total word count M.

The recurrence relation for the maximum gold content is given by:

$$dp[i] = \max_{1 \leq j \leq N \text{ and } i \geq L_j} \{dp[i],\ dp[i-L_j] + B_j\} $$

where \(dp[i]\) represents the maximum gold content achievable with a composition of \(i\) words.

inputFormat

The first line of input contains two integers M and N where M is the total number of words in the composition and N is the number of advanced vocabulary words known by HansBug. Each of the following N lines contains a string A_i (the advanced word), an integer L_i (the number of words it occupies) and an integer B_i (its gold content contribution).

All values are separated by spaces.

outputFormat

A single integer representing the maximum total gold content that can be achieved.

sample

10 2
word1 2 3
word2 3 4

15