Overflowing Gifts

The day after the party, Uk-je found 5,000,500,000,000 gifts that fans had left behind! Moved by this, Uk-je decided to give gifts to the fans too. Too lazy to buy new ones, he only changed the wrapping of the gifts he had received. Still too lazy to do the work himself, he sold some of the gifts and used the money to open a gift wrapping factory.

The $B \times B$ grid factory has a ⊐-shaped conveyor belt along its inner edge. The belt starts at the top left cell of the factory and ends at the bottom left cell. Every second, the belt moves one cell along the ⊐ shape toward the end point. All gifts are carried on this belt, and each time the belt moves one cell, one gift is placed at the start point. The belt is empty at the beginning.

Uk-je hires $N$ workers to wrap $M$ gifts. Workers stand only in cells next to the belt, with at most one person per cell. Worker $i$ takes $T_i$ seconds to wrap one gift. Workers are diligent, so whenever they are not wrapping, they check for an adjacent gift. A worker can wrap any gift on the belt in the four directions up, down, left, and right. If two or more gifts are adjacent, the worker wraps the one that has been on the belt longer. Once all $M$ gifts have been placed at the start point, no new gift is placed there.

Uk-je is a harsh boss and does not allow workers to rest. So a worker who is not wrapping starts wrapping as soon as the belt moves and a gift arrives in an adjacent cell. A wrapped gift is removed from the belt right away, so the gifts behind it can always pass by freely. When a worker finishes, the worker can immediately wrap another gift. A gift that reaches the end point without being wrapped falls off the belt and is discarded.

Look at the example in the figure. The factory is $5 \times 5$, there are 6 gifts, and there are 3 workers. Worker 1 is at $(1, 1)$ and takes $T_1 = 3$ seconds per gift. Worker 2 is at $(1, 3)$ with $T_2 = 2$. Worker 3 is at $(3, 2)$ with $T_3 = 1$. $(r, c)$ is the row and column number, counting from $(0, 0)$. In this case, the workers can wrap 6 gifts in total.

How many gifts can Uk-je deliver to the fans?

The first line contains the factory size $B$ ($4 \le B \le 100$), the number of workers $N$ ($1 \le N \le (3B - 6)$), and the number of gifts $M$ ($1 \le M \le 100$).

From the second line, the next $N$ lines each contain the row $r_i$ ($1 \le r_i \le (B-2)$), the column $c_i$ ($0 \le c_i \le (B-2)$), and the seconds $T_i$ ($1 \le T_i \le 10$) for worker $i$.

Print the maximum number of wrapped gifts that Uk-je can obtain.