You have $$$n+m$$$ points: ($$$x_i$$$, $$$y_i$$$, $$$\text{val}_i$$$). Each point satisfies $$$0 \le x_i \lt n$$$ and $$$0 \le y_i \lt m$$$. $$$\text{val}_i$$$ can be anything from $$$-10^9$$$ to $$$10^9$$$. You are at point $$$(0, 0)$$$ and you want to get to point $$$(n, m)$$$ maximizing your score. You get $$$\text{val}_i$$$ points if the path you go through contains point $$$i$$$ 'below' it. What is the maximum obtainable score?

For further clarification, by a point being 'below' a path, I mean: suppose your path was $$$(0, 0) \rightarrow (x_1, y_1) \rightarrow ... (x_k, y_k) \rightarrow (n, m)$$$. A point $$$(x', y')$$$ will be below this path if there exists a point in the path such that $$$x_i = x'$$$ and $$$y' \le y_i$$$.

Or refer to this image. The red points are below the path and the blue points are above it.

Naive dynamic programming on a grid is an option, of course, but this is at least $$$O(nm)$$$. In this problem, $$$n, m \le 1,000,000$$$ (however, there is a subtask with $$$n, m \le 200,000$$$). I'm looking for a solution with better time complexity, maybe something like $$$O((n + m) log(n + m))$$$ using some kind of sweepline with segment trees. However, I can't figure out how to do this. Can somebody help?