PEG Test - Halloween 2014

Problem C: 2spooky4me

Kenny wants to go trick-or-treating too! But the street has many spooky decorations put up on it. Kenny doesn't like to be scared, so he avoids spooky areas.

There are L houses arranged in a line on the street, numbered from 1 to L. Each house will give exactly 1 unit of candy to Kenny. There are N spooky decorations on this street. The i-th decoration covers the street from house number ai to bi, inclusive, raising the spookiness of those houses by si spookiness units.

Kenny will be too scared to knock on any doors if the spookiness of a house is greater than or equal to S. The spookiness of a house is the sum of the spookinesses of all the decorations passing through it.

Determine the amount of candy Kenny can receive from all the houses on the street.

Input Format

The first line of input will contain the integers: N, L, S (1 ≤ N ≤ 10000; 1 ≤ L ≤ 109; 1 ≤ S ≤ 107).
The next N lines of input will contain values a, b and s for each house. (1 ≤ ai, bi ≤ 109; 1 ≤ si ≤ 1000).

Output Format

Output a single integer, the amount of candy that Kenny can get.

Sample Input 1

3 100 10
20 59 4
30 69 4
40 79 4

Sample Output 1


Explanation 1

Houses between number 40 and 59 inclusive have a spookiness of 12, which is 2spooky for Kenny. He can still get candy from houses 1 to 39, and 60 to 100.

Sample Input 2

2 10 4
3 5 2
5 7 2

Sample Output 2


Explanation 2

Only house 5 is 2spooky for Kenny.

All Submissions
Best Solutions

Point Value: 7
Time Limit: 2.00s
Memory Limit: 16M
Added: Nov 07, 2014
Authors: Alex, frenzybenzy

Languages Allowed:

Comments (Search)

The question can't be done in java because of naming conventions.

Better do it in C++ then.

This is a known issue (granted, it's low priority).