### Vincent Massey SS - 2014 Senior Contest #1

## Problem D: Pillaging

When Zihao isn't doing homework, he likes to go out with his gang and pillage some of the `n` (1 ≤ `n` ≤ 100,000) villages located along a river. Village `i` is located at some position `p _{i}` (1 ≤

`p`≤ 1,000,000,000) along the river, and is either located on the left or the right side of the river. Furthermore, village

_{i}`i`has a payout of

`x`(0 ≤

_{i}`x`≤ 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.

_{i}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 ≤ `t` ≤ 10,000) dollars. Zihao is allowed to have a negative amount of money at any point.

### Input Format

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`, where

_{i}`s`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.

_{i}No two villages will be at the same position.

### Output Format

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.

All Submissions

Best Solutions

**Point Value:** 10 (partial)

**Time Limit:** 5.00s

**Memory Limit:** 16M

**Added:** Nov 04, 2014

**Author:** thorthugnasty

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

IsaacJLon Mar 27, 2016 - 8:23:34 pm UTC HintUsing this test case:

3 1

1 10 0

1 10 1

2 15 1

My code runs through the specific method I have set up, only to return later to continue the recursion with an index of -1, which I never set. I'm not too sure why it's happening.

Any assistance would be appreciated.

spencereiron Mar 28, 2016 - 12:00:07 am UTC Re: HintEDIT: Ignore, as jargon pointed out, this won't occur, the base case will catch the situation where there is nothing left on either side

jargonon Mar 28, 2016 - 12:03:39 am UTC Re: Hintjargonon Mar 28, 2016 - 12:05:18 am UTC Re: Hinttl;dr use local vars thx

IsaacJLon Mar 28, 2016 - 1:35:14 am UTC Re: Hint