Maximizing Shuttle Utilization at the Fair

Farmer John has arranged a shuttle route with N stops (numbered 1 to N) which runs only once. There are K groups of cows. Group i consists of M_i cows wishing to travel from stop S_i to stop E_i (with S_i < E_i). The shuttle has a limited capacity C so it might only pick up part of a group if necessary.

Your task is to maximize the total number of cows that can be transported. For an interval corresponding to a ride from S to E, the cows will occupy each segment from S to E-1. Each of these segments has a capacity limit of C. In other words, if we denote by f_j the number of cows riding on segment j (for 1 ≤ j < N), then the constraint is:

You may pick up a partial group. Compute the maximum total number of cows that can ride the shuttle.

inputFormat

The input consists of a single test case. The first line contains three integers: N, C, and K, where N (2 ≤ N ≤ 20,000) is the number of stops, C (1 ≤ C ≤ 100) is the shuttle capacity, and K (1 ≤ K ≤ 50,000) is the number of cow groups. Each of the following K lines contains three integers: S_i, E_i, and M_i (1 ≤ S_i < E_i ≤ N and 1 ≤ M_i ≤ N), representing that group i has M_i cows wanting to travel from stop S_i to stop E_i.

outputFormat

Output a single integer, the maximum total number of cows that can be transported under the capacity constraints.

sample

10 10 3
1 5 5
3 10 7
5 7 3

13