Ticket Inspection Optimization

Byteasar works as a ticket inspector on an express train running from Byteburg to Bitwise. As part of the recent reform, his salary now depends on the number of different passengers he inspects. To avoid unnecessary work, Byteasar has decided to check tickets exactly $k$ times per ride. Before the journey begins, he receives a summary report which tells him exactly how many passengers travel from one station to another.

The train stops at n stations (numbered from 1 to n). Byteasar can perform a ticket inspection between two successive stations, i.e. at one of the positions 1, 2, ..., n-1. Each inspection checks all passengers riding during that segment. If a group of passengers is checked more than once, they are only counted once. Given the details of m passenger groups, where each group consists of a trip from station a to station b carrying p passengers, determine the maximum number of distinct passengers Byteasar can inspect by choosing exactly $k$ segments for ticket control.

A passenger group traveling from station a to station b is considered inspected if at least one of the chosen inspection positions t satisfies the condition: $$a \le t < b.$$

inputFormat

The input begins with a line containing two integers n and k:

• n (number of stations) where stations are numbered from 1 to n.
• k (exact number of ticket inspections to perform).

The next line contains an integer m, the number of passenger groups. Each of the following m lines contains three integers a, b and p (with 1 ≤ a < b ≤ n) indicating that there are p passengers travelling from station a to station b.

outputFormat

Output a single integer, the maximum number of distinct passengers that can be inspected by choosing exactly $k$ inspection points.

sample

4 1
3
1 3 10
1 4 20
2 4 30

60