Transportation

An express train runs from station A to station B, stopping at several stations along the way. The stations are numbered in order: station A is number $0$ and station B is number $m$. The train can carry at most $n$ passengers, and on every segment of the route the total number of passengers on board must never exceed $n$.

The price of a ticket equals the number of stops between the departure station and the destination station, counting the destination. In other words, a ticket from station $S$ to station $T$ costs $T - S$.

Before the train leaves station A, reservation orders are collected from the intermediate stations. Each order is a triple (departure station $S$, destination station $T$, number of passengers $P$), and the company must either accept an order in full or reject it in full. When the capacity does not allow every order to be accepted, carrying only some passengers of an order is not allowed.

If an order is accepted, its $P$ passengers travel from $S$ to $T$ and therefore occupy every segment in between. The revenue from one accepted order is (number of passengers) $\times$ (ticket price) $= P \times (T - S)$, and the total revenue is the sum over all accepted orders.

Write a program that, given the list of orders, determines the largest total revenue the company can earn.

The input consists of several blocks. The first line of each block contains three integers $n$, $m$, and $k$: the passenger capacity $n$, the number $m$ of station B, and the number $k$ of orders. Each of the next $k$ lines describes one order as three integers $S$, $T$, $P$: the departure station, the destination station, and the number of passengers.

A block contains at most $22$ orders, and the number $m$ of station B is at most $7$. A block whose first line contains three zeros marks the end of the input and is not processed.

For each block except the terminating one, print on its own line the largest total revenue that can be earned.