Vincent Massey SS - 2014 Senior Contest #1

When Zihao isn't doing homework, he likes to go out with his gang and pillage some of the ~n~ ~(1 \le n \le 100\,000)~ villages located along a river. Village ~i~ is located at some position ~p_i~ ~(1 \le p_i \le 1\,000\,000\,000)~ along the river, and is either located on the left or the right side of the river. Furthermore, village ~i~ has a payout of ~x_i~ ~(0 \le x_i \le 10\,000)~ dollars if Zihao decides to pillage it. He starts at position ~0~, on the left side of the river, with ~0~ dollars. His goal is to end up with as much money as possible at the end.

Unfortunately, Zihao is bound by the CCC (Canadian Constitution of Criminals) honour code. Firstly, he can only move from one village to another if the second village is located at a higher position along the river. Thus, he cannot move backwards. Secondly, Zihao can only pillage a city if he is on the same side of the river as the city. However, Zihao can cross the river in his boat at any point and as many times as he wants. Each time Zihao crosses the river, he must pay a tax of ~t~ ~(0 \le t \le 10\,000)~ dollars. Zihao is allowed to have a negative amount of money at any point.

Input Specification

The first line will contain two space-separated integers ~n~ and ~t~.
The next ~n~ lines contain the information for each village in no particular order. Each of these lines will contain three space-separated integers, ~p_i, x_i, s_i~, where ~s_i~ is ~0~ if the village is on the left side of the river and ~1~ if it is on the right side of the river.
No two villages will be at the same position.

Output Specification

Print the largest possible amount of money Zihao can make by pillaging the villages with the restrictions stated above. You may assume that the answer will fit inside of a ~32~-bit integer.

Sample Input

4 10
1 10 0
4 15 0
2 17 1
3 10 1

Sample Output

32

Explanation

The optimal solution is to visit and pillage each city in order of position. You start on the left side of the river. First, pillage the village at position ~1~, giving you ~10~ dollars. Cross to the right side of the river (leaving you with ~0~ dollars) and pillage the village at position ~2~, giving you ~17~ dollars. Then pillage the village at position ~3~, giving you a total of ~27~ dollars. Cross back to the left side of the river (leaving you with ~17~ dollars) and pillage the village at position ~4~, giving you a grand total of ~32~ dollars.