Overview

From rest spots with elevation less than \(X\), select some spots and arrange them so that the elevations in visiting order are strictly decreasing, maximizing the total scenic score. The conclusion is that the optimal strategy is “take all spots that satisfy the conditions and have a positive score.”

Analysis

The key point of this problem is that you can freely decide the visiting order.

• Condition 1: Each spot you visit must have \(A_i < X\)
  → First, the candidates are limited to “spots with elevation lower than \(X\).”

• Condition 2: Elevations must be strictly decreasing in visiting order
  → This looks tricky at first glance, but if you arrange the selected spots in decreasing order of elevation, the condition is always satisfied.
  Since all \(A_i\) are distinct, arranging them in descending order guarantees \(A_{p1} > A_{p2} > \dots\) with strict inequalities.

In other words, there is no difficulty in “how to arrange” the spots to satisfy the conditions. Essentially, it is the same as:

“From spots satisfying \(A_i < X\), you can choose any ones you like, as many as you like.”

Since we want to maximize the total score: - Spots with \(B_i > 0\) are beneficial to include - Spots with \(B_i \le 0\) are detrimental (or provide no benefit) to include

Therefore, selecting all spots satisfying \(A_i < X\) and \(B_i > 0\) is optimal (since not visiting is also an option, negative values can be avoided).

Example: \(X=100\), candidate spots are
- \((A,B)=(90, +5),(80,-3),(70,+10)\)
Then, elevations can be freely arranged in descending order \((90 \to 80 \to 70)\), but it’s better not to include \(-3\), so the answer is \(5+10=15\).

There is no need to naively search for an “optimal decreasing subsequence” with DP, or to mistakenly treat this as an LIS-like problem and implement an \(O(N\log N)\) or \(O(N^2)\) solution (since the order can be freely chosen, such DP approaches are not essential to this problem).

Algorithm

1. Initialize \(ans=0\).
2. For each spot \((A_i, B_i)\):
   • If \(A_i < X\) and \(B_i > 0\), then \(ans \leftarrow ans + B_i\)
3. Output \(ans\).

This achieves “take only the profitable ones among all spots satisfying the conditions.”

Complexity

• Time complexity: \(O(N)\) (just one pass through each spot)
• Space complexity: \(O(1)\) (processing input sequentially, no additional arrays needed)

Implementation Notes

• Since \(N\) can be up to \(2\times 10^5\), in Python it is safe to use sys.stdin.buffer.read() for fast input.

• To reliably exclude negative scores and spots with \(A_i \ge X\), it is clearest to write the condition directly as if A < X and B > 0:.

  Source Code

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    N = int(next(it))
    X = int(next(it))
    ans = 0
    for _ in range(N):
        A = int(next(it))
        B = int(next(it))
        if A < X and B > 0:
            ans += B
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.