この問題はDPで解くことができます。

各 \(m=1,2,\ldots\) に対して「最小何円で \(m\) 個の山に登ることができるか」を求めることができれば元の問題に答えることができます。

\(\mathrm{dp}[i][j]\) を「 \(i\) 番目の山を \(j\) 個目に登頂するときの、その時点までの入山料の最小値（不可能なら \(\infty\)）」とします。

\(i\) 番目の山に登るとき、直前に登ったのがどの山であるか考えることで、遷移は次の通りになります。

\(\mathrm{dp}[i][j]=\begin{cases} C_i & j=1 \text{ のとき}\\ \min\{\mathrm{dp}[\mathrm{pre}][j-1]+C_i\mid \mathrm{pre}<i, S_{\mathrm{pre}}<S_i\} & j > 1 \text{ のとき} \\ \end{cases}\)

（ただし空集合に対する min は \(\infty\) とする）

この DP は状態数が \(O(NK)\) 、各状態の計算が \(O(N)\) 時間のため、 \(O(N^2K)\) 時間で全体の計算を行うことができます。

元の問題の答えは \(\min_i \mathrm{dp}[i][m]\leq B\) となる最大の \(m\) になります。

実装例 (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, k, b;
  cin >> n >> k >> b;
  int INF = 1e9;

  vector<int> c(n), s(n);
  for(int i=0; i<n; i++) cin >> c[i] >> s[i];

  vector<vector<int>> dp(n, vector<int>(n+1, INF));

  for(int i=0; i<n; i++){
    dp[i][1] = c[i];
    for(int j=2; j<=n; j++){
      int best = INF;
      for(int pre=0; pre<i; pre++){
        if(s[pre] < s[i]){
          best = min(best, dp[pre][j-1] + c[i]);
        }
      }
      dp[i][j] = best;
    }
  }

  for(int x=min(n,k); x>=0; x--){
    int best = INF;
    for(int i=0; i<n; i++){
      best = min(best, dp[i][x]);
    }
    if(best <= b){
      cout << x << endl;
      break;
    }
  }
}

実装例 (Python)

N, K, B = map(int,input().split())
INF = 10**9

dp = [[INF]*(N+1) for _ in range(N)]
C, S = [], []
for _ in range(N):
  c, s = map(int,input().split())
  C.append(c)
  S.append(s)

for i in range(N):
  dp[i][1] = C[i]
  for j in range(2, N+1):
    dp[i][j] = min((dp[pre][j-1] + C[i] for pre in range(i) if S[pre]<S[i]), default=INF)

for x in range(min(N,K), -1, -1):
  if min(dp[i][x] for i in range(N)) <= B:
    print(x)
    break