最大复合

题目描述

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

对于由 $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$

输出格式

将答案作为整数输出。

样例

3 2
2 3
1 5
4 2

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$。

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

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$）
• 所有输入值均为整数。