Miner Seok
Time limit1sMemory limit512 MB
Choose an axis-aligned rectangle anchored at (0,0) whose interior minerals number at most C, maximizing the total beauty of the minerals inside it.
- Level
Hard8 of 10
- Topics
- Sorting, Binary search, Prefix sum, Implementation
- Solved
- No attempts yet
Problem
There are N minerals. The i-th mineral is at (Xi, Yi), its mining cost is 1, and its beauty is Vi.
Seok is at (0, 0). A born miner, Seok is about to use his signature skill, "mine flip." When he uses it, he can mine every mineral inside a rectangular region that has his current position as a corner and has any height H (H ≥ 0) and width W (W ≥ 0). Minerals on the boundary of the region must also be mined.
Every mineral inside the rectangular region must be mined. If the total mining cost of the minerals in the region is greater than the money C he currently has, he goes bankrupt.
If Seok goes bankrupt, he cannot mine any minerals, and the resulting butterfly effect lowers Korea's employment rate. The higher the total beauty of the minerals Seok obtains, the higher Korea's employment rate rises. For everyone's happiness, maximize the total beauty of the minerals Seok can obtain without going bankrupt.
Input
The first line gives the number of minerals N and the money Seok has, C.
The next N lines give three integers each: the i-th line contains Xi, Yi, Vi. These are the X and Y coordinates of the i-th mineral and its beauty.
Output
Print the maximum total beauty of the minerals Seok can obtain without going bankrupt.
Constraints
1 ≤ N ≤ 500,000
0 ≤ Xi, Yi ≤ 100,000
1 ≤ Vi ≤ 10^8
1 ≤ C ≤ N
All minerals are at distinct positions, and no mineral is at (0, 0). Every number given is an integer.