Shopping in the Server's System Store

lcy0x1 goes to the server's system store to purchase items. A person has a backpack with $21$ slots. Initially, his backpack contains $m$ different items which cannot be sold. He wants to buy $n$ types of items. For the $i$-th item, its name is $st_i$, the available quantity is $a_i$, the value per piece is $b_i$, and each slot can hold up to $c_i$ pieces. Items of the same type can be stored in the same slot (as long as the slot is not full).

Objective: Determine the maximum total revenue he can earn in one run. Note that the initial $m$ items occupy $m$ slots, leaving $21-m$ slots available for new items.

inputFormat

The first line contains two integers $m$ and $n$, where $m$ ($0 \le m \le 21$) represents the number of different items initially in the backpack (which cannot be sold) and $n$ is the number of item types available in the system store.

Each of the next $n$ lines contains a string $st_i$ and three integers $a_i$, $b_i$, $c_i$, representing the name of the item, the available quantity, the value per piece, and the capacity per slot for that item, respectively.

outputFormat

Output a single integer representing the maximum total revenue that can be earned in one run.

sample

1 1
apple 100 5 10

500