#P1502. Maximizing the Window's Star Brightness

    ID: 14788 Type: Default 1000ms 256MiB

Maximizing the Window's Star Brightness

Maximizing the Window's Star Brightness

At night, Little Ka looks out from the balcony and exclaims, "Wow~~~~ so many stars!" However, he has not yet installed a window in the other room. Ever the optimist, Little Ka wishes to see as many bright stars as possible at night. His window has a fixed size and its edges must remain parallel to the ground.

Using his special ability (x-ray vision), Little Ka can see the position and brightness of every star behind the wall. However, the ability tires him out, so he asks you to determine the maximum total brightness of stars that can appear in the window.

The window is an axis-aligned rectangle with a fixed width and height. A star is considered visible if it lies within or on the boundary of the window.

Formally, you are given an integer n representing the number of stars. You are also given the window's width w and height h. Each of the next n lines contains three integers x, y and b denoting the position (x, y) of a star and its brightness. Find the maximum sum of brightness of the stars that can be covered by a window when it is optimally positioned.

The condition for a star at position (x, y) to lie inside a window with bottom-left corner (L, B) is given by: \[ L \le x \le L + w, \quad B \le y \le B + h. \]

inputFormat

The first line contains a single integer n (number of stars).
The second line contains two integers w and h representing the width and height of the window.
Each of the next n lines contains three integers x, y, and b describing a star's position and brightness.

outputFormat

Output a single integer representing the maximum possible total brightness of the stars that can be covered by the window.

sample

3
3 2
1 1 5
2 2 3
4 3 10
13