COCI '17 Contest 7 #3 Go

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

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

Ilica is, as we all know, the longest street in Zagreb. There are N houses on the same side of the street, and each house has a house number between 1 and N. The competition begins at house number K.

Before the competition, Branimirko looked at the map and saw M Pokémon. Each Pokémon is located at its (distinct) house number Ai, is valued at Bi candy, and can be caught only in the next Ti seconds, after which it disappears from the map and is impossible to catch.

Branimirko can visit one house number per second. Also, when he catches a Pokémon, that Pokémon disappears from the map.

Since Branimirko really likes candy, he asked for your help. Help him and determine the maximal amount of candy he can get!

Input Specification

The first line of input contains integers N,K (1KN1000) and M (1M100), the number of houses, the starting house number and the number of Pokémon.

Each of the following M lines contains integers Ai (1AiN), Bi (1Bi100) and Ti (1Ti2000) from the task.

In the input data, the Pokémon will always be in a strictly ascending order by house number Ai.

Output Specification

You must output the required maximal amount of candy from the task.

Scoring

In test cases worth 20% of total points, it will hold M10.

In additional 20% of total points, it will hold M20.

Sample Input 1

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

Sample Output 1

Copy
115

Explanation for Sample Output 1

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).

Sample Input 2

Copy
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

Copy
172

Comments

There are no comments at the moment.