AT_abc366_f [ABC366F] Maximum Composition

题目描述

给定 $N$ 个一次函数 $f_1, f_2, \ldots, f_N$，其中 $f_i(x) = A_i x + B_i$。

对于由 $K$ 个 $1$ 到 $N$ 之间互不相同的整数构成的长度为 $K$ 的数列 $p = (p_1, p_2, \ldots, p_K)$，请你求出 $f_{p_1}(f_{p_2}(\ldots f_{p_K}(1)\ldots ))$ 能取得的最大值。

输入格式

输入以如下格式从标准输入给出。

$N$ $K$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

输出格式

请输出一个整数，表示答案。

输入输出样例 #1

输入 #1

3 2
2 3
1 5
4 2

输出 #1

26

输入输出样例 #2

输入 #2

10 3
48 40
34 22
24 37
45 40
48 31
49 44
45 40
44 6
35 22
39 28

输出 #2

216223

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^{5}$
• $1 \leq K \leq \min(N, 10)$
• $1 \leq A_i, B_i \leq 50$ （$1 \leq i \leq N$）
• 输入均为整数

样例解释 1

对于所有可能的 $p$ 及其对应的 $f_{p_1}(f_{p_2}(1))$ 的值如下：

• $p = (1, 2)$：$f_1(f_2(1)) = 15$
• $p = (1, 3)$：$f_1(f_3(1)) = 15$
• $p = (2, 1)$：$f_2(f_1(1)) = 10$
• $p = (2, 3)$：$f_2(f_3(1)) = 11$
• $p = (3, 1)$：$f_3(f_1(1)) = 22$
• $p = (3, 2)$：$f_3(f_2(1)) = 26$

因此，输出 $26$。

由 ChatGPT 4.1 翻译