I Don't Want to Work

Farmer Jay owns a farm with $N$ cells and wants to grow various fruits from day $0$ to day $M$.

Each day, Jay can do the following at any cell.

• Plant a seed. If the cell already has a fruit, remove it and plant a new seed.
• Harvest a fruit.

Jay can grow $K$ kinds of fruit. The information for the $i$-th kind is as follows.

• It takes $A_i$ days for a seed to grow and bear its first fruit.
• After a harvest, the fruit grows back after $B_i$ days.
• Each harvest yields one fruit, and selling a fruit earns $C_i$ money.

Jay wants to earn as much money as possible.

Jay can do as much work as desired each day, and has plenty of seeds of each fruit.

The first line contains $N$, $M$, and $K$ separated by spaces. $(1\le N \le 1000, 1\le M \le 50, 1 \le K \le 100)$

The next $K$ lines contain $A_i$, $B_i$, and $C_i$ for the $i$-th fruit, separated by spaces. $(1 \le A_i, B_i \le 50, 1 \le C_i \le 1000)$

Print the maximum money Jay can earn by day $M$.