Description

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?

Input Format

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$.

Output Format

The maximum amount of money $s$.

20 3
63 1 64 yinshifen
1 10 1 men
1 1 64 yinshifen

64

Hint

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<c_i\leq 64$；
• $0<|st_i|<100$；
• $0\leq s\leq 10^6$。

Note: The testdata is strong. Brute-force search scores $0$. Please use the bounded knapsack.

Translated by ChatGPT 5