Overview

We look at the mountain peaks from left to right, selecting at most \(K\) of them such that their elevations are strictly increasing, and find the “maximum number of peaks that can be selected” while keeping the total entrance fee at most \(B\).

Analysis

This problem resembles the Longest Increasing Subsequence (LIS) due to the conditions “proceed in ascending order of indices” and “elevations of selected peaks must be increasing.” However, in this problem, we not only want to maximize the length, but each peak also has a cost \(C_i\), with the constraint that the total must not exceed the budget \(B\).

• A brute-force approach of trying all “select/don’t select” combinations would be \(2^N\), which is far too slow for \(N \le 500\).
• Even with tricks like “sort by elevation…”, the constraint that we must proceed in order of peak indices (\(i_1 < i_2 < \cdots\)) means a DP that “extends from a previous peak” is the natural approach.
• The key observation here is that if we maintain “the minimum cost to form an increasing subsequence of length \(l\)”, we can determine whether it fits within the budget \(B\).
  In other words, we transform the “maximize length” problem into a “find the minimum cost for each length” problem.

Algorithm

We define the DP as follows:

• \(dp[i][l] =\) the minimum total entrance fee needed to form a strictly increasing elevation subsequence of length \(l\) that ends at peak \(i\)
  (treated as \(\infty\) if it cannot be formed)

The transition is similar to LIS, in the form of “extending from a previous peak \(j\).”

1. Initialization

   • Selecting peak \(i\) alone:
     \(dp[i][1] = C_i\)

2. Transition

   • When \(j < i\) and \(S_j < S_i\), we can append \(i\) after the subsequence ending at peak \(j\):
     \(dp[i][l] = \min\left(dp[i][l],\ dp[j][l-1] + C_i\right)\)
     
   • To simplify the budget check, values exceeding \(B\) are treated as \(\infty\) (in the code, as \(B+1\)).

3. Updating the answer

   • If \(dp[i][l] \le B\) holds for some \(i\), then length \(l\) is achievable.
     The answer is the maximum such \(l\) (with \(l \le K\)).

Concrete Example (Illustration)

For instance, when we want to form “a subsequence of length 2 ending at \(i\)”: - Among peaks \(j\) to the left of \(i\), - find those satisfying \(S_j < S_i\), - and pick the one that minimizes \(dp[j][1] + C_i\).

Extending this to lengths \(3, 4, \dots\) is exactly what this DP does.

Complexity

• Time complexity: \(O(N^2 K)\)
  (For each \(i\), we examine all \(j < i\) and update lengths \(2..K\))
• Space complexity: \(O(NK)\)
  (the \(dp\) array)

Within the constraints, this is approximately \(500^2 \times 50 = 12{,}500{,}000\), which is well within the time limit.

Implementation Notes

• \(\infty\) only needs to represent the state “exceeded the budget \(B\)”, so in the code we set INF = B + 1 (this makes the <= B check straightforward).

• The upper limit on the number of peaks climbed is \(K\), but naturally it cannot exceed \(N\), so we set L = min(K, N).

• If dp[j][l-1] is already > B, adding more cost is pointless, so we skip it to reduce the constant factor.

• Since the answer can end at any peak, we check dp[i][l] <= B for each \(i\) and update the maximum \(l\).

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K, B = map(int, input().split())
    C = [0] * N
    S = [0] * N
    for i in range(N):
        c, s = map(int, input().split())
        C[i] = c
        S[i] = s

    L = min(K, N)
    INF = B + 1

    dp = [[INF] * (L + 1) for _ in range(N)]
    ans = 0

    for i in range(N):
        ci = C[i]
        dpi = dp[i]
        dpi[1] = ci
        if ci <= B:
            ans = max(ans, 1)

        si = S[i]
        for j in range(i):
            if S[j] < si:
                dpj = dp[j]
                # length 2..L
                for l in range(2, L + 1):
                    prev = dpj[l - 1]
                    if prev <= B:
                        val = prev + ci
                        if val > B:
                            val = INF
                        if val < dpi[l]:
                            dpi[l] = val

        for l in range(2, L + 1):
            if dpi[l] <= B and l > ans:
                ans = l

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.