## Pillaging

View as PDF

Points: 10 (partial)
Time limit: 2.5s
Memory limit: 16M

Author:
Problem types
##### 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 villages located along a river. Village is located at some position along the river, and is either located on the left or the right side of the river. Furthermore, village has a payout of dollars if Zihao decides to pillage it. He starts at position , on the left side of the river, with 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 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 and .
The next lines contain the information for each village in no particular order. Each of these lines will contain three space-separated integers, , where is if the village is on the left side of the river and 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 -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 , giving you dollars. Cross to the right side of the river (leaving you with dollars) and pillage the village at position , giving you dollars. Then pillage the village at position , giving you a total of dollars. Cross back to the left side of the river (leaving you with dollars) and pillage the village at position , giving you a grand total of dollars.