Go
레이팅 미적용의견: 0
1 \(s / 512\) \(MB / 100\) points
Branimirko is still a passionate player of the wor\(ld-re\)nowned 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 \(A\) {i}{ }, is valued at \(B\) _{i} candy, and can be caught only in
the next \(T\) {i}{ } 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!
In test cases worth 20% of total points, it will hold \(M\) ≤ 10.
In additional 20% of total points, it will hold \(M\) ≤ 20.
1 \(s / 512\) \(MB / 100\) points
The first line of input contains integers N, \(K\) (1 ≤ \(K\) ≤ \(N \le 1\,000\)) and \(M\) (1 ≤ \(M \le 100\)), the
number of houses, the starting house number and the number of Pokémon.
Each of the following \(M\) lines contains integers \(A\) {i}{ }(1 ≤ \(A\) {i} ≤ \(N\) ), \(B\) (1 ≤ \(B\) {i} ≤100) and \(T\) ≤} (1 ≤ \(T\) _{i
2 000) from the task.
In the input data, the Pokémon will always be in a strictly ascending order by house number
\(A\) {i}{ }.
You must output the required maximal amount of candy from the task.
10 5 4
1 30 4
3 5 7
7 10 12
9 100 23
20 8 7
1 35 14
4 57 1
6 32 2
9 94 28
14 78 8
15 8 1
17 55 3output
115
172Clarification of the first test 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).
평가 및 의견
Go
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Go