When \(K\) integers used for the sequence \(p\) is fixed, what kind of property does \(p\) have? An important fact is as follows:

The ordering of \(f_i(f_j(x))\) and \(f_j(f_i(x))\) is independent of \(x\), and solely dependent on the ordering of \(\frac{A_i-1}{B_i}\) and \(\frac{A_j-1}{B_j}\). If \(\frac{A_i-1}{B_i}>\frac{A_j-1}{B_j}\), then \(f_i(f_j(x))>f_j(f_i(x))\).

By this property, given \(K\) integers to be used for \(p\), the value \(f_{p_1}(f_{p_2}(\ldots f_{p_K}(1) \ldots))\) takes on the maximum value when \(p\) satisfies \(\frac{A_{p_1}-1}{B_{p_1}} \geq \frac{A_{p_2}-1}{B_{p_2}} \geq \ldots \geq \frac{A_{p_K}-1}{B_{p_K}}\).

For simplicity, suppose that \((A,B)\) are sorted so that \(\frac{A_1-1}{B_1} \geq \frac{A_2-1}{B_2} \geq \ldots \frac{A_N-1}{B_N}\).

Then the problem can be rephrased as follows:

Find the maximum \(f_{p_1}(f_{p_2}(\ldots f_{p_K}(1) \ldots))\) for a sequence \(p\) of integers between \(1\) and \(N\) such that \(p_1 <p_2< \ldots <p_N\).

This problem can be solved with the following DP (Dynamic Programming):

\(dp_{i,j}=( \) the maximum value of \(f_{p_{K-i}}(\ldots f_{p_K}(1)\ldots)\) when \(p_K,p_{K-1},\ldots p_{K-i}\) are decided so that \(p_{K-i} \geq j\) \()\).

Specifically, the transition goes like \(dp_{i,j}=\text{max}(dp_{i,j+1},A_j \times dp_{i-1,j+1}+B_j)\), and the sought answer is \(dp_{K,1}\).

Since there are \(O(NK)\) states and each transition costs \(O(1)\), the problem can be solved in a total of \(O(NK)\) time.

Sample code (C++):

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
    }
    vector<int> ord(n);
    for (int i = 0; i < n; ++i)
        ord[i] = i;
    sort(ord.begin(), ord.end(), [&](int i, int j) { return b[i] * (a[j] - 1) > b[j] * (a[i] - 1); });
    vector<long long> dp(k + 1, -1e9);
    dp[0] = 1;
    for (auto i : ord) {
        vector<long long> ndp = dp;
        for (int j = 0; j < k; ++j) if(dp[j] != -1e9) {
            ndp[j + 1] = max(ndp[j + 1], dp[j] * a[i] + b[i]);
        }
        dp = move(ndp);
    }
    cout << dp[k] << "\n";
}

Sample code (Python):

n, k = map(int, input().split())
a = []
b = []
for _ in range(n):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)

ord_indices = list(range(n))
ord_indices.sort(key=lambda i: (a[i] - 1) / b[i])

dp = [int(-1e9)] * (k + 1)
dp[0] = 1

for i in ord_indices:
    ndp = dp[:]
    for j in range(k):
        if dp[j] > int(-1e9):
            ndp[j + 1] = max(ndp[j + 1], dp[j] * a[i] + b[i])
    dp = ndp

print(dp[k])