P5052 [COCI 2017/2018 #7] Go

Branimirko 是世界著名游戏 Pokémon Go 的一位热情玩家。最近，他决定组织一场抓小精灵的比赛。比赛将在 Zagreb 的 Ilica 大街举行，主要赞助商是他的朋友 Slavko。奖励当然是糖果! 我们都知道，Ilica 是 Zagreb 最长的街道。在街道的同一侧有 $N$ 栋房子，房子从左到右分别依次有 $1$ 到 $N$ 的门牌号。 比赛前，Branimirko 看了看地图，发现了一共有 $M$ 只小精灵。每个小精灵都位于自己的各不相同的房子里，第 $i$ 个房子门牌号为 $A_i$，小精灵价值 $B_i$ 个糖果，并且只能在 $T_i$ 秒内被抓，之后它就会从地图上消失。 Branimirko 第 $1$ 秒在门牌号为 $K$ 的房子。接下来每一秒它可以移动到门牌号相邻的房子，或者不移动。当他在一个时刻和一只小精灵处在相同的房子时，他就会抓住这只小精灵，获得其对应的糖果，且这只小精灵就从地图上消失了。 因为 Branimirko 真的很喜欢糖果，所以他请求你的帮助。 帮助他求出他可以得到多少糖果。

无

无

In test cases worth 20% of total points, it will hold M ≤ 10. In additional 20% of total points, it will hold M ≤ 20. **Clarification 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).