P1964 【MC Survival】Selling Items

The server is fun.

lcy0x1 goes to the server’s system shop to sell items. A player’s backpack has $21$ slots. Initially, his backpack contains $m$ different item types (cannot be sold), which occupy $m$ slots. He wants to sell $n$ types of items. For the $i$-th type with name $st_i$, there are $a_i$ items, each worth $b_i$, and up to $c_i$ items can be stacked in one slot. Identical items can be put in the same slot as long as it is not full. Question: In one run, what is the maximum amount of money he can sell?

The first line contains two integers $m, n$. Each of the next $n$ lines contains three integers $a_i, b_i, c_i$ and a string $st_i$.

The maximum amount of money $s$.

Constraints: - $0\leq m\leq 21$； - $0\leq n\leq 100$； - $0\leq a_i\leq 1344$； - $0\leq b_i\leq 10^4$； - $0