If the upper-left ¹⁄₄ part of the convex hull of chosen grid points is fixed, the set of chosen points are determined automatically. Thus, by processing the input grid points in their lexicographical (ascending) order, we can apply a dynamic programming approach with focusing on the last two points forming the upper-left part. Specifically, let \(\mathrm{dp}(p, q)\) be the optimal value when the last segment forming the upper-left part of the convex hull is \((p, q)\), and compute them as follows:

\[\mathrm{dp}(p_1, q) = \max_{p_2} \{\, \mathrm{dp}(p_2, p_1) + \mathrm{add}(p_1, q) \mid \text{slope of}~(p_2, p_1) \ge \text{slope of}~(p_1, q) \,\}.\]

Note that the slopes of the segments forming the upper-left part of the convex hull are nonpositive and monotonically decreasing, and that you should take a horizontal segment intersecting the Y-axis when you add the first point. \(\mathrm{add}(p_1, q)\) is the sum of the scores of grid points that should be newly added (i.e., that is in the trapezoid below the segment \((p_1, q)\)), which depends only on the current point and the last point, so we can precompute that values for all the pairs in advance. The total computational time is \(\mathrm{O}(N^3)\).