Treasure Collection

After finally cracking a millennium‐old mystery, little FF discovered the royal treasury filled with countless treasures. However, his collection vehicle has a maximum weight capacity of \(W\), and there are \(n\) types of treasures available. Each treasure type has a value \(v_i\), a weight \(w_i\), and there are \(m_i\) pieces of each available. Little FF wants to load his vehicle with a selection of treasures so that the total value is maximized while keeping the total weight within \(W\).

This is a bounded knapsack problem. Each item is available in a limited quantity, and you may use techniques such as binary decomposition to efficiently process the items.

inputFormat

The first line contains two integers: \(W\) (the maximum weight capacity of the vehicle) and \(n\) (the number of treasure types).

The next \(n\) lines each contain three integers: \(v_i\) (the value of the \(i\)th treasure), \(w_i\) (the weight of the \(i\)th treasure), and \(m_i\) (the number of available pieces for the \(i\)th treasure).

outputFormat

Output a single integer, the maximum total value of the treasures that can be loaded into the vehicle without exceeding the weight \(W\).

sample

10 2
6 2 3
10 3 2

32