Saving the Ryan Statue
Time limit3sMemory limit1024 MB
Choose one integer point on each side of an N by N square to form a smaller rectangle, maximizing the total value of statues it covers, including those on its border.
- Level
Medium6 of 10
- Topics
- Array, Prefix sum, Brute force, Implementation
- Solved
- No attempts yet
Problem
Bryan owns a square plot of land. For convenience, place the bottom-left corner of this land at (0, 0), and let each side be parallel to either the X-axis or the Y-axis.
Inside this land there are M statues in total, counting both Ryan statues and Brown statues. The border of the land has a fence, so no statue lies on it. One day, bryan learns that kazel is planning to attack his land. Because kazel attacks from the corner positions of the land, bryan decides to erect one pillar at an integer coordinate position on each side, excluding the corners, and connect the pillars to build a new rectangular fence, creating a new plot of land protected from kazel's attacks.
Bryan assigns each statue a value Vi and wants to maximize the sum of the values of the statues included in the new land. A statue on the fence of the new land is also included in the new land.
Also, because kazel targets the Brown statues when attacking, bryan wants to avoid including Brown statues in the new land as much as possible, to reduce the risk of kazel attacking again. Therefore, these Brown statues are assigned non-positive values. (Naturally, Ryan statues are assigned positive values.)
Bryan is busy preparing the material to paint the new fence, so you must compute for him how the new fence should be built.
Input
The first line gives N, the side length of the land bryan originally owns, and M, the number of statues. Each of the following M lines gives the position Xi, Yi and the value Vi of one statue.
- 2 ≤ N ≤ 500
- 1 ≤ M ≤ 500
- 0 < Xi, Yi < N
- -10^5 ≤ Vi ≤ 10^5
Output
Print the maximum sum of the values of the statues included in a new land built to satisfy the conditions.