E :: Training Private Ryan

Time Limit: 1 Second    Memory Limit: 32768 KB

Private Ryan is taking the training of his military service. As part of the training, he participates in a session where he must shoot a number of targets quickly using an M-4 rifle. Each target appears at a specific moment of time and will disappear at some moment in future. Furthermore, each target is assigned a specific score, and Ryan can shoot a target more than once. There is a reloading time L for the rifle, so there should be at least L time steps between any consecutive shots. When he decides to shoot, he can choose one of the targets being present at the moment. What is the biggest score Ryan can achieve, assuming that he can use at most n bullets?

Input

There are multiple test cases in the input. Each test case starts with 3 numbers n (the number of bullets), L (the rifle reloading time), and k (the number of targets) in a line. The following k lines contain description of the targets. Each target is described by three numbers; appearing time (ta), disappearing time (td) and its score (s). Ryan can shoot the target in the closed interval [ta , td] with ta < td. Note that all of the input numbers are non-negative integers, where n <= 100 and L <= 10⁹, and for each target, 0 <= ta < td <= 10⁹. The scores are not greater than 1,000,000 and k <= 1000. The last line of the input contains three zeros which should not be processed.

Output

For each test case, write a single line in the output containing the maximum possible score that Ryan can achieve.

Sample Input

4 2 3
2 7 8
1 3 6
0 12 3
2 10 3
1 2 3
2 10 5
10 11 3
0 0 0

Sample Output

30
6

Submit

Source: Tehran, Asia Region - Regional 2011