103665: [Atcoder]ABC366 F - Maximum Composition

Problem Statement

You are given $N$ linear functions $f_1, f_2, \ldots, f_N$, where $f_i(x) = A_i x + B_i$.

Find the maximum possible value of $f_{p_1}(f_{p_2}(\ldots f_{p_K}(1) \ldots ))$ for a sequence $p = (p_1, p_2, \ldots, p_K)$ of $K$ distinct integers between $1$ and $N$, inclusive.

Constraints

• $1 \leq N \leq 2 \times 10^{5}$
• $1 \leq K \leq \text{min}(N,10)$
• $1 \leq A_i, B_i \leq 50$ $(1 \leq i \leq N)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer as an integer.

Sample Input 1

3 2
2 3
1 5
4 2

Sample Output 1

26

Here are all possible $p$ and the corresponding values of $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$

Therefore, print $26$.

Sample Input 2

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

Sample Output 2

216223

问题陈述

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

找到一个序列$p = (p_1, p_2, \ldots, p_K)$，其中包含K个不同的整数，范围在1到N之间（包括1和N），使得$f_{p_1}(f_{p_2}(\ldots f_{p_K}(1) \ldots ))$的值最大。

约束条件

• $1 \leq N \leq 2 \times 10^{5}$
• $1 \leq K \leq \text{min}(N,10)$
• $1 \leq A_i, B_i \leq 50$（$1 \leq i \leq N$）
• 所有输入值都是整数。

输入

输入从标准输入以以下格式给出：

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

输出

将答案打印为一个整数。

示例输入1

3 2
2 3
1 5
4 2

示例输出1

26

以下是所有可能的$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$。

示例输入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