Problem Description

Branimirko is a passionate player of the world-renowned game Pokémon Go. Recently, he decided to organize a competition in catching Pokémon. The competition will be held on Ilica Street in Zagreb, and the main sponsor is his friend Slavko. The reward is, of course, candy!

Ilica Street is the longest street in Zagreb. There are \( N \) houses on the same side of the street, numbered from 1 to \( N \). The competition begins at house number \( K \).

Before the competition, Branimirko looked at the map and found \( M \) Pokémon. Each Pokémon is located at a distinct house number \( A_i \), valued at \( B_i \) candy, and can be caught only within \( T_i \) seconds, after which it disappears from the map.

Branimirko starts at the house number \( K \) at the first second. Each subsequent second, he can move to an adjacent house number or stay in the same house. When he is at the same house as a Pokémon, he can catch it, obtaining the corresponding candy, and the Pokémon disappears from the map.

Since Branimirko really likes candy, he asked for your help. Help him determine the maximum amount of candy he can collect.

Input Format

The first line of input contains three integers \( N \), \( K \) (\( 1 \leq K \leq N \leq 10^3 \)) and \( M \) (\( 1 \leq M \leq 100 \)), representing the number of houses, the starting house number, and the number of Pokémon, respectively.

The following \( M \) lines each contain three integers \( A_i \) (\( 1 \leq A_i \leq N \)), \( B_i \) (\( 1 \leq B_i \leq 100 \)), and \( T_i \) (\( 1 \leq T_i \leq 2000 \)), indicating the house number, the candy value, and the time limit for each Pokémon. The Pokémon are given in strictly ascending order by house number \( A_i \).

Output Format

Output the maximum amount of candy Branimirko can collect.

Notes/Hints

In test cases worth 20% of the total points, \( M \leq 10 \).

In additional 20% of the total points, \( M \leq 20 \).

Sample Input and Output

Sample Input #1

10 5 4
1 30 4
3 5 7
7 10 12
9 100 23

Sample Output #1

115

Sample Input #2

20 8 7
1 35 14
4 57 1
6 32 2
9 94 28
14 78 8
15 8 1
17 55 3

Sample Output #2

172

Explanation of the First Sample Case

One strategy is that Branimirko first catches the Pokémon at house number 3 (5 candy), then, respectively, house numbers 7 (10 candy) and 9 (100 candy) for a total of 115 candy.

Notice that Branimirko can’t catch the Pokémon at house number 1, because he can’t reach it in time from his starting position (house number 5).

见题面 Input 部分

见题面 Output 部分